This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2995 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../datastructure/unionfind.cpp" #include "../../tree/sack.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; int n,k; cin>>n>>k; vector<int> us(n),vs(n),cs(n),ds(n); for(int i=1;i<n;i++) cin>>us[i]>>vs[i]; for(int i=0;i<n;i++) cin>>cs[i]>>ds[i]; int num=0; vector<int> cnt(k,0); UnionFind uf(k); auto calc=[&](int c){return min(cnt[c],uf.size(c));}; auto expand=[&](int v){ int c=uf.find(cs[v]); int d=uf.find(ds[v]); int flg=uf.same(c,d); if(flg){ num-=calc(c); uf.unite(c,d); cnt[c]++; num+=calc(c); }else{ num-=calc(c)+calc(d); uf.unite(c,d); if(uf.find(c)!=c) swap(c,d); cnt[c]+=cnt[d]+1; num+=calc(c); } }; auto shrink=[&](int v){ num=0; cnt[cs[v]]=cnt[ds[v]]=0; uf.ps[cs[v]]=cs[v]; uf.ps[ds[v]]=ds[v]; uf.rs[cs[v]]=uf.rs[ds[v]]=1; }; vector<int> ans(n); auto query=[&](int v){ans[v]=num;}; Sack S(n,expand,shrink,query); for(int i=1;i<n;i++){ us[i]--;vs[i]--; S.add_edge(us[i],vs[i]); } for(int i=0;i<n;i++){ cs[i]--,ds[i]--; S.add_query(i,i); } S.build(); for(int i=0;i<n;i++) cout<<ans[i]<<newl; return 0; }
#line 1 "test/aoj/2995.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2995 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "datastructure/unionfind.cpp" #line 3 "datastructure/unionfind.cpp" using namespace std; #endif //BEGIN CUT HERE struct UnionFind{ int num; vector<int> rs,ps; UnionFind(int n):num(n),rs(n,1),ps(n,0){ iota(ps.begin(),ps.end(),0); } int find(int x){ return (x==ps[x]?x:ps[x]=find(ps[x])); } bool same(int x,int y){ return find(x)==find(y); } void unite(int x,int y){ x=find(x);y=find(y); if(x==y) return; if(rs[x]<rs[y]) swap(x,y); rs[x]+=rs[y]; ps[y]=x; num--; } int size(int x){ return rs[find(x)]; } int count() const{ return num; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "tree/sack.cpp" #line 3 "tree/sack.cpp" using namespace std; #endif //BEGIN CUT HERE struct Sack{ using F = function<void(int)>; vector<int> sub,hvy,big; vector< vector<int> > G,Q; F expand,shrink,query; Sack(int n,F expand,F shrink,F query): sub(n,1),hvy(n,-1),big(n,0),G(n),Q(n), expand(expand),shrink(shrink),query(query){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void add_query(int v,int k){ Q[v].emplace_back(k); } void add(int v,int p,int x){ if(x==1) expand(v); else shrink(v); for(int u:G[v]) if(u!=p and !big[u]) add(u,v,x); } void dfs(int v=0,int p=-1,bool k=0){ for(int u:G[v]) if(u!=p and u!=hvy[v]) dfs(u,v,0); if(~hvy[v]){ dfs(hvy[v],v,1); big[hvy[v]]=1; } add(v,p,1); for(int k:Q[v]) query(k); if(~hvy[v]) big[hvy[v]]=0; if(!k) add(v,p,0); } void build(int v=0,int p=-1){ for(int u:G[v]){ if(u==p) continue; build(u,v); if(hvy[v]<0 or sub[hvy[v]]<sub[u]) hvy[v]=u; sub[v]+=sub[u]; } if(p==-1) dfs(v,p); } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/aoj/2995.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); const char newl = '\n'; int n,k; cin>>n>>k; vector<int> us(n),vs(n),cs(n),ds(n); for(int i=1;i<n;i++) cin>>us[i]>>vs[i]; for(int i=0;i<n;i++) cin>>cs[i]>>ds[i]; int num=0; vector<int> cnt(k,0); UnionFind uf(k); auto calc=[&](int c){return min(cnt[c],uf.size(c));}; auto expand=[&](int v){ int c=uf.find(cs[v]); int d=uf.find(ds[v]); int flg=uf.same(c,d); if(flg){ num-=calc(c); uf.unite(c,d); cnt[c]++; num+=calc(c); }else{ num-=calc(c)+calc(d); uf.unite(c,d); if(uf.find(c)!=c) swap(c,d); cnt[c]+=cnt[d]+1; num+=calc(c); } }; auto shrink=[&](int v){ num=0; cnt[cs[v]]=cnt[ds[v]]=0; uf.ps[cs[v]]=cs[v]; uf.ps[ds[v]]=ds[v]; uf.rs[cs[v]]=uf.rs[ds[v]]=1; }; vector<int> ans(n); auto query=[&](int v){ans[v]=num;}; Sack S(n,expand,shrink,query); for(int i=1;i<n;i++){ us[i]--;vs[i]--; S.add_edge(us[i],vs[i]); } for(int i=0;i<n;i++){ cs[i]--,ds[i]--; S.add_query(i,i); } S.build(); for(int i=0;i<n;i++) cout<<ans[i]<<newl; return 0; }