Codeforces #157 div1E Little Elephant and Tree
URL:http://www.codeforces.com/contest/258/problem/E
問題概要
N頂点からなる全域木がある。根は頂点1。
それぞれの頂点はあるリストを持っている。
M回処理をする。i番目の処理は、
頂点uiより下の部分木、頂点viより下の部分木 の頂点すべてのリストに、数iを入れる。
処理が終わったら、それぞれの頂点について、
自分以外の頂点で、リストに一つでも同じ数を含む頂点の数を求めよ。
N<=100000
方針
segtreeで解けます。
ある頂点xとリストに同じ数を含む頂点は、xの子孫とも同じ数を含む、ということに注意。
まず、euler-tourをして、segtreeを建てます。
それぞれの頂点で、処理のui,viのどちらかになっているなら、もう片方の頂点の部分木の範囲に+1します。
また、自分の頂点の部分木にも+1します。
それぞれの頂点で、segtreeの列の上で正の数を持っている要素の数を求めます。
これが、同じ数をもつ頂点に対応します。
ただし、値が正になったら必ず自分を含んでいるので-1します
上の処理は、segtreeがそれぞれのノードで、
「子に伝播させていない変更」「区間の最小値」「区間の最小値を取る要素の数」
を覚えれば、なんとかできます。
O(NlogN)
using namespace std; static const int INF =500000000; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; struct segtree{ int n,n2; int val[400005],mini[400005],lazy[400005]; void init(int n_){ n2=n_; n=1; while(n<n_) n<<=1; for(int i=0;i<n_;++i){ mini[i+n-1]=0; val[i+n-1]=1; } for(int i=n-2;i>=0;--i){ mini[i]=0; val[i]=val[i*2+1]+val[i*2+2]; } } void add(int a,int b,int i,int l,int r,int v){ if(a<=l && r<=b){ lazy[i]+=v; mini[i]+=v; return; } if(b<=l || r<=a) return; int md=(l+r)>>1; if(lazy[i]){ lazy[i*2+1]+=lazy[i]; mini[i*2+1]+=lazy[i]; lazy[i*2+2]+=lazy[i]; mini[i*2+2]+=lazy[i]; lazy[i]=0; } add(a,b,i*2+1,l,md,v); add(a,b,i*2+2,md,r,v); mini[i]=min(mini[i*2+1],mini[i*2+2]); val[i]=0; if(mini[i]==mini[i*2+1]) val[i]+=val[i*2+1]; if(mini[i]==mini[i*2+2]) val[i]+=val[i*2+2]; } int query(){ if(mini[0]==0) return n2-val[0]; return n2; } }; segtree seg; int n,m,cnt; int begin[100005],end[100005]; vector<int> g[100005]; void dfs(int v,int p){ begin[v]=cnt++; for(int i=0;i<g[v].size();++i){ int to=g[v][i]; if(to==p) continue; dfs(to,v); } end[v]=cnt; } vector<int> connect[100005]; int ans[100005]; void dfs2(int v,int p){ for(int i=0;i<connect[v].size();++i){ int to=connect[v][i]; seg.add(begin[to],end[to],0,0,seg.n,1); } ans[v]=seg.query(); if(ans[v]>0) --ans[v]; for(int i=0;i<g[v].size();++i){ int to=g[v][i]; if(to==p) continue; dfs2(to,v); } for(int i=0;i<connect[v].size();++i){ int to=connect[v][i]; seg.add(begin[to],end[to],0,0,seg.n,-1); } } int main(){ cin>>n>>m; for(int i=0;i<n-1;++i){ int a,b;scanf("%d%d",&a,&b);--a;--b; g[a].push_back(b); g[b].push_back(a); } dfs(0,-1); for(int i=0;i<m;++i){ int a,b;scanf("%d%d",&a,&b);--a;--b; connect[a].push_back(b); connect[b].push_back(a); connect[a].push_back(a); connect[b].push_back(b); } seg.init(n); dfs2(0,-1); for(int i=0;i<n;++i) printf("%d ",ans[i]); putchar('\n'); return 0; }
CFのEでsegtreeが出ておきながら解かないor解けないのさすがにどうにかしたい