test/yukicoder/2085.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:41:24+09:00
• Problem: https://yukicoder.me/problems/2085

Depends on

• ReRooting (tree/rerooting.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/2085"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tree/rerooting.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  auto fold=[](int a,int b){return max(a,0)+max(b,0);};
  auto lift=[](int a,int d){return d-a;};
  ReRooting<int, int> G(n,fold,lift,0);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G.add_edge(a,b,1);
  }
  auto res=G.build();

  vector<int> ans;
  for(int i=0;i<n;i++)
    if(1-res[i]>0) ans.emplace_back(i);

  cout<<ans.size()<<"\n";
  for(int x:ans) cout<<x+1<<"\n";
  cout<<flush;
  return 0;
}

#line 1 "test/yukicoder/2085.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/2085"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tree/rerooting.cpp"

#line 3 "tree/rerooting.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T, typename Edge>
struct ReRooting{
  struct Node{
    int to,rev;
    Edge data;
    Node(int to,Edge data):to(to),data(data){}
    bool operator<(const Node &v)const{return to<v.to;};
  };

  using Fold = function<T(T, T)>;
  using Lift = function<T(T, Edge)>;

  vector< vector<Node> > G;
  vector< vector<T> > ld,rd;
  vector<int> lp,rp;

  const Fold fold;
  const Lift lift;
  const T id;

  ReRooting(int n,const Fold fold,const Lift lift,const T id):
    G(n),ld(n),rd(n),lp(n),rp(n),fold(fold),lift(lift),id(id){}

  void add_edge(int u,int v,Edge d,Edge e){
    G[u].emplace_back(v,d);
    G[v].emplace_back(u,e);
  }

  void add_edge(int u,int v,Edge d){add_edge(u,v,d,d);}

  // k: idx for edge (not vertex)
  T dfs(int v,int k){
    while(lp[v]!=k and lp[v]<(int)G[v].size()){
      auto &e=G[v][lp[v]];
      ld[v][lp[v]+1]=fold(ld[v][lp[v]],lift(dfs(e.to,e.rev),e.data));
      lp[v]++;
    }
    while(rp[v]!=k and rp[v]>=0){
      auto &e=G[v][rp[v]];
      rd[v][rp[v]]=fold(rd[v][rp[v]+1],lift(dfs(e.to,e.rev),e.data));
      rp[v]--;
    }
    if(k<0) return rd[v][0];
    return fold(ld[v][k],rd[v][k+1]);
  }

  int search(vector<Node> &vs,int idx){
    return lower_bound(vs.begin(),vs.end(),Node(idx,vs[0].data))-vs.begin();
  }

  vector<T> build(){
    int n=G.size();
    for(int i=0;i<n;i++){
      sort(G[i].begin(),G[i].end());
      ld[i].assign((int)G[i].size()+1,id);
      rd[i].assign((int)G[i].size()+1,id);
      lp[i]=0;
      rp[i]=(int)G[i].size()-1;
    }

    for(int i=0;i<n;i++)
      for(Node &t:G[i])
        t.rev=search(G[t.to],i);

    vector<T> res;
    for(int i=0;i<n;i++)
      res.emplace_back(dfs(i,-1));

    return res;
  }

  // p: idx for vertex
  T subtree(int v,int p){
    int k=search(G[p],v);
    assert(k<(int)G[p].size() and G[p][k].to==v);
    return lift(dfs(v,G[p][k].rev),G[p][k].data);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/yukicoder/2085.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  auto fold=[](int a,int b){return max(a,0)+max(b,0);};
  auto lift=[](int a,int d){return d-a;};
  ReRooting<int, int> G(n,fold,lift,0);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G.add_edge(a,b,1);
  }
  auto res=G.build();

  vector<int> ans;
  for(int i=0;i<n;i++)
    if(1-res[i]>0) ans.emplace_back(i);

  cout<<ans.size()<<"\n";
  for(int x:ans) cout<<x+1<<"\n";
  cout<<flush;
  return 0;
}

Back to top page