题解：CF1984E Shuffle

· · 题解

E

把一个点的父亲儿子都加到 T_2 后，这个点就是叶子，且与之直接相连的点都不是叶子。（所有相邻点都是这个点的祖先）。

所有的叶子构成一个独立集，我们找去除根后最大的，类似上司的舞会。

枚举每个节点作为初始的根，换根 dp。如果根本身就是叶子还要在加一。

具体来说，第一次扫描以 1 为根求出 f_{x, 1/0} 表示以 x 为根的子树中 x 选/不选的最大独立集：

\begin{cases}f_{x, 0} = \sum_{y \in g_x} \max(f_{y, 0}, f_{y, 1}) \\ f_{x, 1} = \sum_{y \in g_x} f_{y, 0}\end{cases}

第二次扫描求出 h_{x, 1/0} 表示选/不选 x 的最大独立集，h_{1, 0/1} = f_{1, 0/1}：

\begin{cases}h_{x, 0} = \max(h_{fa, 1},\ f_{x, 0} + (h_{fa, 0} - \max(f_{x, 1}, f_{x, 0})))\\h_{x, 1} = f_{x, 1} + (h_{fa, 0} - \max(f_{x, 1}, f_{x, 0})) \end{cases}

用 h_{x, 0} + [x \texttt{ is leaf}] 更新答案。

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; ++ i) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y);
        g[y].eb(x);
    }
    vector<array<int, 2>> f(n + 1, {0, 0});
    auto dfs = [&](auto &&dfs, int x, int fa) -> void {
        f[x][0] = 0;
        f[x][1] = 1;
        for(int y : g[x]) {
            if(y != fa) {
                dfs(dfs, y, x);
                f[x][0] += max(f[y][0], f[y][1]);
                f[x][1] += f[y][0];
            }
        }
    };
    dfs(dfs, 1, 0);
    vector<array<int, 2>> h(n + 1);

    h[1][0] = f[1][0];
    h[1][1] = f[1][1];
    int ans = h[1][0] + (g[1].size() == 1);

    auto dfs2 = [&](auto &&dfs2, int x, int fa) -> void {
        int tmp = h[fa][0] - max(f[x][0], f[x][1]);
        h[x][1] = f[x][1] + tmp; 
        h[x][0] = max(h[fa][1], f[x][0] + tmp);
        tmp = h[x][0] + (g[x].size() == 1);
        ans = max(ans, tmp);
        for(int y : g[x]) {
            if(y != fa) {
                dfs2(dfs2, y, x);
            }
        }
    };
    for(int y : g[1]) {
        dfs2(dfs2, y, 1);
    }
    cout << ans << '\n';
}