(多分)典型だけど非常に良い問題だと感じたので覚え書きも兼ねて…
Submission #2253114 - AtCoder Regular Contest 028
ソースコード
問題
N頂点の木が与えられるので、木の各頂点に対してその頂点を削除した場合の最大の連結成分の大きさを答えよ
制約:N<=105
部分点:N<=103を満たすテストケースが通れば30点
解法
部分点解法
REP(i,N)で頂点iを削除した場合の最大の連結成分の大きさをN回シミュレートする
連結成分の大きさの計算はBFSだったりDFSだったりUnionFindで行える
計算量はO(N2)とかO(N2 logN)とかO(N2 α(N)) (αはアッカーマン関数の逆関数)とか
N<=103なら十分間に合う
満点解法
木DPで解いてみる
考察
まずは適当な頂点を根とした時の頂点iの部分木について考える
ある頂点を削除した時の連結成分の大きさを知りたい訳だから、部分木の大きさを持つと楽になりそう
そこで、dp[i]:頂点iの部分木に含まれる頂点の数 とする
頂点iが葉の場合は、dp[i]=1になる
もし頂点iから伸びている辺があるなら、その先の頂点(頂点jとする)の値を加算すればいいので、dp[i]=1+dp[j]となる
頂点iから複数の辺が伸びている場合は、その先の頂点が持つ値を全て加算する事になる
このようにして配列dpを埋め終わった後、連結成分の大きさを出すためにはどうすればよいか考えてみる
頂点iを削除する事により、どのような連結成分ができるかを考える
まずは木の根を含む連結成分ができる事がわかる これの大きさはN-dp[i]で求める事ができる
また、頂点iから伸びる辺と繋がっていた頂点を含む別の連結成分が、頂点iから伸びていた辺の数だけできる事もわかる
頂点iから伸びていた辺の先にある頂点を頂点jとすると、これの大きさはdp[j]で出せる事がわかる
そのため、これらの連結成分のうちの最大値を出力すればいい事が分かった
実装
まずは適当な頂点(今回は頂点0にした)を決めて、その頂を根とする有向木を作る
BFSで頂点0と任意の頂点との距離を求め(頂点0と頂点iの距離をrange[i]とする)、頂点0との距離が小さい方から大きな方へと辺を繋げていく
その後にpriority_queue
キューの先頭から取り出していって、dp[i]を計算した後にans[i]を計算する
そして配列ansの値を順番に出力していったものが答えとなる
