問題文は一見ややこしいが、意図を理解すれば簡単。
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とかはスタックでかいのであまり気にならないけど…。