木からパスへ (Tree--->path) [Summer Festival Contest 2018 D]

https://beta.atcoder.jp/contests/summerfes2018-div1/tasks/summerfes2018_d

考察過程

1. 最小パス被覆かな？と一瞬思うが、この方針でいくとWA
2. この方針ではない時に考えられるのは木DPくらい
3. パスの状況も追加で保存しておく必要がありそう
4. 正直、あまり自信はないけど、実装してみると通る

解法

https://beta.atcoder.jp/contests/summerfes2018-div1/submissions/3071026

木DPをする
dfs(cu) = 頂点cuを根とした部分木を改変して作れるパスの中で
{端点が頂点cuにあるパス, 端点が頂点cuにないパス}を作るための最小頂点個数
　
dfsの中で更にDPをしよう。
dp[cnt] := 頂点cuを根とした部分木を改変して作れるパスの中で頂点cuの次数が
cntであるパスを作るための最小頂点個数
DP更新式は以下の通り。
　
pd[0] = dp[0] + min(p.first, p.second) + 1;
頂点cuには接続せず、後々接続するパスにくっつける
　
pd[1] = min(dp[1] + min(p.first, p.second) + 1, dp[0] + p.first);
「頂点cuには接続せず、もともと1つくっついてるパスにくっつける」と「頂点cuに接続する」の最小値を採用
　
pd[2] = min(dp[2] + min(p.first, p.second) + 1, dp[1] + p.first);
「頂点cuには接続せず、もともと2つくっついてるパスのどちらかにくっつける」と
「頂点cuに接続する」の最小値を採用

int N;
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
pair<int, int> dfs(int cu, int pa = -1) { // {端点1, 端点2}
    vector<int> dp = { 0, 0, 0 }; // {端点0, 端点1, 端点2}
    fore(to, E[cu]) if (to != pa) {
        vector<int> pd = { 0, 0, 0 };
        auto p = dfs(to, cu);
 
        pd[0] = dp[0] + min(p.first, p.second) + 1;
        pd[1] = min(dp[1] + min(p.first, p.second) + 1, dp[0] + p.first);
        pd[2] = min(dp[2] + min(p.first, p.second) + 1, dp[1] + p.first);
 
        swap(dp, pd);
    }
 
    return { dp[1], dp[2] };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
 
    auto p = dfs(0);
    int ans = min(p.first, p.second);
    cout << ans << endl;
}