AtCoder ARC #028 : C - 高橋王国の分割統治

問題文は一見ややこしいが、意図を理解すれば簡単。
http://arc028.contest.atcoder.jp/tasks/arc028_3

問題

N頂点から木を成したグラフが与えられる。
ある頂点vにおける「バランス値」とは、その頂点vを経由せず互いに行き来できる最大の頂点群の要素数である。
各頂点に対するバランス値を答えよ。

解法

バランス値の定義を言い換えると、各頂点vにつながる各辺について、辺の先にある頂点数の最大値になる。
適当に根となる頂点を定めてDFSをしていくと、子の頂点数はDFSで簡単に求められる。また、親側の辺の向こうにある頂点数は、N-1-(全ての子の頂点数)なのでこれも簡単に求められる。
これらのなかで最大値を答えればよい。

なお、今回の入力例では、各頂点に対する親頂点の番号が与えられ、かつ親頂点の方の番号が小さい。
よって頂点番号の大きな順に処理を行うと、再帰を使うことなく簡単に書ける。

int N;
vector<int> E[100010];

int NN[100100],P[100100],B[100100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		E[x].push_back(i+1);
	}
	
	for(i=N-1;i>=0;i--) {
		NN[i]=1;
		FOR(j,E[i].size()) {
			NN[i]+=NN[E[i][j]];
			B[i]=max(B[i],NN[E[i][j]]);
		}
		B[i]=max(B[i],N-NN[i]);
	}
	FOR(i,N) _P("%d\n",B[i]);
}

まとめ

この入力形式における再帰を使わない方法は、再帰しすぎのスタック溢れに有効だね。
CFとかはスタックでかいのであまり気にならないけど…。