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解けないのさすがにどうにかしたい