概要

サイズがNの根付き木が与えられる。木の根は頂点1。 AliceとBobはこの木でゲームをする。

木の各頂点には最初はすべてコインが1枚ずつ置かれている。最初に駒を用意し、頂点1(根)に置く。手番はAliceから始まり、AliceとBobが交互に行動する。 2人はともに以下の条件で動く。

この時、Aliceの獲得するコインは何枚？

制約：$ 1 \leq N \leq 10 ^ 5 $

考え方

この問題は問題名の通り、DFSをするかのように駒は動くとわかる。この時、明らかに親頂点での計算結果は子頂点にのみ依存することから、木DPをすることが大筋となる。

すべての葉(子を持たない頂点)を、葉から見た初めての分かれ道までの距離を見てみる。例えば、

(1) -- (2) --- (3) -- (4) -- (5) -- (6)
        |
        ------ (7) -- (8) -- (9)

の頂点(6)は、枝分かれ(2)までの距離は4であり、頂点(9)は、枝分かれまでの距離が3である。

最初に、Bob(後手)が頂点(6)の方を選択すると、頂点(6)から(2)へ戻るときは、Alice-Bob-Alice-Bobであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点での選択権はAliceに渡ることになる。これは、最初の枝分かれまでの距離が偶数の場合である。

最初に、Bob(後手)が頂点(9)の方を選択すると、頂点(9)から(2)へ戻るときは、Alice-Bob-Aliceであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点でも選択権は相変わらずBobにある。これは、最初の枝分かれまでの距離が奇数の場合である。

すべての枝分かれの先は個のように単純に葉につながってる構造ではないものの、ひとまずこれで葉に直結する分かれ道に関しての利得やコントロール権の変遷を計算できた。葉に直結する枝分かれで、コントロール権を持つ人は、

できるならば相手にコントロール権を押し付けたい(自分がコインをもらえるので)
コントロール権を押し漬けられるような子が複数個あるなら、相手が得られるコインの数(つまり枝分かれから葉までの距離)が最小になるものから選ぶ
コントロール権が変わる枝分かれがすべてなくなったとき、コントロール権がある人が残りのコントロール権が変わらない子をめぐることになり、結果的にこの時点でコントロールできない人は残りの子のコインをすべてもらえることになる。

これは、葉に直結する分かれ道の話だったが、一般の分かれ道にもこの話を帰着させよう。同様に、子へ行くことによるコントロール権の移り変わりがあるかに着目して、先ほどの考察を広げる。

以下のようにDPテーブルを定める。

dp[i] := 頂点iを始めて訪れた時、双方適切に行動して、コントロール権を持った人の得られるコイン-持ってない人の得られるコイン

お互いにコイン数を最大化したいので、これはどの方にとっても、獲得量の差の最大化でもある。

これを使って、先ほどの葉に直結する場合例では$ dp[3] = -4, dp[7] = -3 $である。(選ぶと相手が獲得し、自分が獲得できないため)

この一般化した時のコントロール権にまつわるアルゴリズムは以下である。

コントロール権の変化がある子$ x $の場合、$ dp[x] $が大きい順(コントロール権がある人から見て、相手より一杯とれる順)に使う。
コントロール権の変化がない子の場合、$ dp[x] > 0 $なら最初にコントロール権がある人が全部使う。(使ってもコントロール権が向こうに行かないので、全部取るのが最適)
コントロール権の変化がない子で、$ dp[i] \leq 0 $の場合、使っても行き損である。(相手が得するのみならず、コントロール権も押し付けられない)これは最後の最後までAliceもBobも取りたくない。

このことから、子の$ dp[x], dp[y], \cdots $がそろった時に、親の$ dp[a] $(頂点$ a $を初めて訪れた時に、コントロール権を持つ人の獲得コイン-持たない人の獲得コイン)は次のように計算すればよい。

コントロール権が変わらない子$ x $に関して、$ dp[x] > 0 $の$ dp[x] $をすべて$ dp[a] $に加算。
コントロール権が変わる子$ x $に関して、$ dp[x] $が小さい順に並べ、1, 3, 5, ...番目は加算(自分がとるため)、2, 4, 6, ...番目は減算(相手がとるため)する。
最後に、コントロール権を持つ人がコントロール権不変の$ dp[x] \leq 0 $の子をすべて取る。

これをすべての分かれ道について、再帰的に計算することでこの問題は解くことができた。

計算量についてだが、木DPなのですべての頂点を1度は見ることなり、$O(n)$である。また、分かれ道では以上のアルゴリズムを行うためにソートをする必要があるが、この部分ではたかだか$O(n \log n)$なので、解くことができた。

C++　いろいろわかりやすい？コメントがついてる。ちょっと冗長。

コンテスト中に正しい考察してたのに詰め切ることができなかった。お前実装力足りてたらすぐに青上位だぞ精進しろ。