AT_abc223_g [ABC223G] Vertex Deletion

思路

显然我们需要求出原树的最大匹配。

定义 $dp_{i,0/1}$ 表示在 $i$ 为根的子树中进行匹配，且 $i$ 不选/选 的最大匹配。状态转移方程比较显然：

$$\left\{\begin{matrix} dp_{u,0} = \sum{val_v}\\ dp_{u,1} = (\sum{val_v}) - val_t + dp_{t,0} + 1 \end{matrix}\right.$$

其中 $val_u = \max(dp_{u,0},dp_{u,1})$，然后 $t$ 是使得 $dp_{u,1}$ 最大的一个 $v$。显然这一步是可以 $\Theta(n)$ 计算的。

注意到，我们需要计算删除 $u$ 后的最大匹配，这等同于计算以 $u$ 为根时的 $dp_{u,0}$。于是考虑换根 DP。

令当前的根由 $u$ 转为 $v$。接下来只需简单分讨，记转移 $dp_{u,1}$ 时的 $t$ 为 $id_u$，$dp_{t,0} - val_t + 1$ 为 $Max_u$。

由于 $v$ 由 $u$ 的儿子变为了父亲，$dp_u$ 的值一定发生变化。显然 $dp_{u,0} \leftarrow dp_{u,0} - val_v$。其次：

1. 当 $id_u = v$ 时：$dp_{u,1} \leftarrow dp_{u,0} - dp_{v,1} - 1$，然后和其次大值进行匹配。因此还需在第一次 DFS 时处理出次大的儿子。

2. 否则：$dp_{u,1}$ 直接减去 $val_v$ 即可。

然后可以更新 $val_u \leftarrow \max(dp_{u,0},dp_{u,1})$。接下来更新 $dp_v$。

显然的是 $dp_{v,0/1}$ 都需要加上 $val_u$。

其次，如果 $Max_v$ 小于 $u$ 带来的贡献，那么更新掉即可。需要注意的是，$id_v,Max_v$ 以及维护的次大值都需要被更新。

这样就完成了所有元素的更新，继续向下换根即可。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 2e5 + 10,M = 4e5 + 10,inf = 1e9 + 10;
int n,ans;
int idx,h[N],ne[M],e[M];
int res,dp[N][2],val[N],Max[2][N],id[2][N];
// 这里 Max[0/1] 和 id[0/1] 分别维护的是最小值和次小值

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void add(int a,int b){
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}

inline void dfs1(int u,int fa){
    int mMax = -inf,fMax = -inf;
    int mid = 0,fid = 0;
    val[u] = dp[u][0] = dp[u][1] = 0;
    for (re int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if (j == fa) continue;
        dfs1(j,u);
        dp[u][0] += val[j];
        dp[u][1] += val[j];
        int t = dp[j][0] - val[j] + 1;
        if (mMax < t){
            fMax = mMax; fid = mid;
            mMax = t; mid = j;
        }
        else if (fMax < t){
            fMax = t; fid = j;
        }
    }
    Max[0][u] = mMax; Max[1][u] = fMax;
    id[0][u] = mid; id[1][u] = fid;
    dp[u][1] += max(0,mMax);
    val[u] = max(dp[u][0],dp[u][1]);
}

inline void dfs2(int u,int fa){
    ans += (dp[u][0] == res);
    for (re int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if (j == fa) continue;
        int dpu0 = dp[u][0],dpu1 = dp[u][1],valu = val[u];
        int Max0u = Max[0][u],Max1u = Max[1][u],id0u = id[0][u],id1u = id[1][u];
        int dpj0 = dp[j][0],dpj1 = dp[j][1],valj = val[j];
        int Max0j = Max[0][j],Max1j = Max[1][j],id0j = id[0][j],id1j = id[1][j];
        dp[u][0] -= val[j];
        if (id[0][u] == j){
            dp[u][1] -= (dp[j][0] + 1);
            if (id[1][u]) dp[u][1] += Max[1][u];
        }
        else dp[u][1] -= val[j];
        val[u] = max(dp[u][0],dp[u][1]);
        dp[j][0] += val[u]; dp[j][1] += val[u];
        int t = dp[u][0] - val[u] + 1;
        if (Max[0][j] < t){
            dp[j][1] -= Max[0][j];
            Max[1][j] = Max[0][j]; id[1][j] = id[0][j];
            Max[0][j] = t; id[0][j] = u;
            dp[j][1] += Max[0][j];
        }
        else if (Max[1][j] < t){
            Max[1][j] = t; id[1][j] = u;
        }
        dfs2(j,u);
        dp[u][0] = dpu0; dp[u][1] = dpu1; val[u] = valu;
        Max[0][u] = Max0u; Max[1][u] = Max1u; id[0][u] = id0u; id[1][u] = id1u;
        dp[j][0] = dpj0; dp[j][1] = dpj1; val[j] = valj;
        Max[0][j] = Max0j; Max[1][j] = Max1j; id[0][j] = id0j; id[1][j] = id1j;
    }
}


int main(){
    memset(h,-1,sizeof(h));
    n = read();
    for (re int i = 1;i < n;i++){
        int a,b; a = read(),b = read();
        add(a,b); add(b,a);
    }
    dfs1(1,0); res = val[1];
    dfs2(1,0);
    printf("%d",ans);
    return 0;
}