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)

。

代码

CPP

#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;
}

CF2050G Tree Destruction 题解

文章操作

思路

代码

相关推荐

评论

CF2050G Tree Destruction 题解