CF2050G Tree Destruction 题解

· · 题解

题目传送门

思路

设 dp_{u,0/1/2} 分别代表以 u 为根的子树中，选择的路径不经过 u / 其中一个端点为 u / u 在这条路径上，但不为其端点可以得到的连通块的最大数量。

如果删掉的路径不包含 u，直接分类讨论每一个儿子的情况即可：

dp_{u,0} = \max_v \{dp_{v,0}, dp_{v,1} + 1, dp_{v,2} + 1\}

如果删掉的路径中 u 为端点，则除了儿子 v 一起被删，其他的儿子会被分为不同的连通块。所以：

dp_{u,1} = \max_v \{dp_{v,1} + cnt - 1\}

其中 cnt 为 u 的儿子个数，-1 是为了减少 v 节点。

如果删掉的路径中 u 在这条路径上，但不为其端点，则 u 有 2 个儿子也一定在这条路径上，那就可以理解为将一条以 u 为端点的路径和一条以 u 的一个儿子 v 为端点的路径合并在一起，即：

dp_{u,2} = \max_v\{dp_{u,1} + dp_{v,1} - 1\}

因为需要用到 dp_{u,1}，所以在 dp_{u,1} 更新前先更新 dp_{u,2}。时间复杂度 \mathcal{O}(n)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int t, n;
int dp[N][3];
vector<int> tr[N];

void dfs(int u, int fa)
{
    int cnt = 0;
    for (int v : tr[u])
        if (v != fa) cnt++;
    dp[u][0] = 0, dp[u][1] = dp[u][2] = cnt;
    for (int v : tr[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] = max({dp[u][0], dp[v][0], max(dp[v][1], dp[v][2]) + 1});
        dp[u][2] = max(dp[u][2], dp[u][1] + dp[v][1] - 1);
        dp[u][1] = max(dp[u][1], dp[v][1] + cnt - 1);
    }
}

void solve()
{
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1, 0);
    printf("%d\n", max({dp[1][0], dp[1][1], dp[1][2]}));
    for (int i = 1; i <= n; i++)
        tr[i].clear();
}

int main()
{
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}