Codeforces ECR #002 : E. Lomsat gelral

ここらへんまで来るとEducationalというか普通の問題っぽい。
http://codeforces.com/contest/600/problem/E

問題

根付き木が与えられる。
各頂点には色が塗られている。

各頂点について、そのsubtree中における最多登場の色番号を答えよ。

解法

頂点毎に、subtreeにおける色番号とその登場回数をmapで管理する。また登場回数の最大値を管理する。
あとは葉からマージテクを使いmapをマージしていき、最多登場回数の色をその都度答えればよい。

int N;
int C[101010];
vector<int> E[101010];

map<int,int> M[101010];
int mnum[101010];
ll S[101010];

void dfs(int cur,int pre) {
	int mar=-1;
	FORR(r,E[cur]) if(r!=pre) {
		dfs(r,cur);
		if(mar==-1 || M[r].size()>M[mar].size()) mar=r;
	}
	if(mar!=-1) swap(M[cur],M[mar]), mnum[cur]=mnum[mar], S[cur]=S[mar];
	FORR(r,E[cur]) if(r!=pre) {
		FORR(rr,M[r]) {
			int x = M[cur][rr.first] += rr.second;
			if(x > mnum[cur]) mnum[cur]=x, S[cur]=0;
			if(x == mnum[cur]) S[cur]+=rr.first;
		}
	}
	int x = M[cur][C[cur]] += 1;
	if(x > mnum[cur]) mnum[cur]=x, S[cur]=0;
	if(x == mnum[cur]) S[cur]+=C[cur];
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	FOR(i,N) cout<<S[i]<<" ";
	cout<<endl;
	
}

まとめ

マージテクを知ってるとすんなりだけど、知らないと辛そうな問題。