Codeforces ECR #047 : F. Dominant Indices

遅れて参加したのでさすがに間に合いませんでした。
http://codeforces.com/contest/1009/problem/F

問題

根付き木が与えられる。
各頂点に対し、以下を答えよ。

• その頂点のSubTree内の頂点を、頂点からの距離でグループ化したとき、最大数となる距離のうち最小値

解法

各頂点において、その頂点からの距離に対応した頂点数をカウントした可変長配列を、マージテクの要領でマージしていきながら最大値を数えていくだけ。
頂点数が10^6と割と多いので、dequeを使ったらMLEした。

int N;
vector<int> Q[1010101];
int ret[1010101];
vector<int> E[1010101];

void dfs(int cur,int pre) {
	int ma=1,id=0;
	Q[cur].push_back(1);
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		Q[e].push_back(0);
		if(Q[e].size()>Q[cur].size()) {
			swap(Q[e],Q[cur]);
			id=ret[e]+1;
			ma=Q[cur][Q[cur].size()-1-id];
		}
	}
	int x;
	FORR(e,E[cur]) if(e!=pre) {
		FOR(x,Q[e].size()) {
			Q[cur][Q[cur].size()-1-x]+=Q[e][Q[e].size()-1-x];
			if(Q[cur][Q[cur].size()-1-x]>ma || (Q[cur][Q[cur].size()-1-x]==ma && x<id)) ma=Q[cur][Q[cur].size()-1-x], id=x;
		}
		Q[e].clear();
	}
	
	ret[cur]=id;
}

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

まとめ

これ10^5でよくない？