Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 1

codeforces.com
木に関する考察や操作がいまいちなので、今まで解いた問題含めて復習です。
内容はdarkshadowsさんが書いてくれた木DPの記事の（自分用）まとめです。
基本的に引用記事を和訳したものとなっています。
全部で問題1~5があり、本記事は問題1のまとめです。

問題１．
「n個の頂点を持つ木が与えられます。各頂点i(1<=i<=n)にはCi個のコインが置かれています。隣接する頂点を選ばずにコインを取る頂点を選択したとき、得られるコインの枚数の最大値はいくつか。」

この問題と似たパターンとして、n個の要素を持つ一次元配列の場合があります。この場合は、
dp(i)=max(Ai+dp(i-2), dp(i-1))
と定義して、再帰的に計算すれば良いです。配列の場合は、このように「1番目～i番目のindexまでを考えたときに得られるコインの枚数の最大値」をdp(i)と定義すれば良いですね。

さて、木でこの問題を考える場合、dp(i)を「iを根とする部分木から得られるコインの枚数の最大値」と定義する必要があります。すると、木全体の根を頂点1としたとき、最終的な答えはdp(1)となりますね。

画像がでか過ぎてごめんなさい（）
さて、dp(i)をより詳しく定義しましょう。
配列の場合は「直前のindexのコインを取るかどうか」で場合分けしましたね。木の場合は、「子の頂点のコインを取るかどうか」で場合分けです。着目する頂点をV、子の頂点をv1, v2, ... vn、子の頂点の子を「孫」としておきます。
このとき、ポイントとなるのは「子の頂点のどれかのコインを取ると、頂点Vのコインは取れない」ことです。

配列の場合はi番目を考えるとき、i-1番目を取るかどうかを考えればよかったですね。
しかし、木の場合は頂点Vを考えるとき、頂点v1, v2, ... vnのすべてを考える必要があり、さすがに場合分けしてられません。
そこで、次のようにdpを二つ定義することとします（頂点Vを根とする部分木を「部分木V」と表記します）。

dp1(V):=頂点Vにあるコインを取るときの、部分木Vから得られるコインの枚数の最大値
dp2(V):=頂点Vにあるコインを取らないときの、部分木Vから得られるコインの枚数の最大値

すると、
dp1(V)=Cv+∑(i=1~n){dp2(vi)}
//子の頂点viのコインを取ってはいけませんよ。
dp2(V)=∑(i=1~n){ max(dp1(vi), dp2(vi)}
//頂点Vのコインを取らないので、子の頂点viのコインはとっても取らなくても良いですね。
となります。

実装をコードで確認しましょう。元記事のコードがとてもきれいだったので、そのまま載せています。

//グラフは隣接リストで管理
vector<int> adj[N];

int dp1[N],dp2[N];

//頂点pVは頂点Vの親
void dfs(int V, int pV){

    //dp1とdp2に代入する数をsum1, sum2に一時的に保管しておきます。
    int sum1=0, sum2=0;

    //頂点Vの子の頂点vを見ていきます。
    for(auto v: adj[V]){
    if(v == pV) continue; //親はスルーします。
    dfs(v, V);
    sum1 += dp2[v];
    sum2 += max(dp1[v], dp2[v]);
    }

    dp1[V] = C[V] + sum1;
    dp2[V] = sum2;
}

int main(){
    int n;
    cin >> n;

    for(int i=1; i<n; i++){
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    }

    dfs(1, 0);
    int ans = max(dp1[1], dp2[1]);
    cout << ans << endl;
}