题解：P10794 『SpOI - R1』架子鼓可以站 C

题目大意

可以任意进行多次操作，每次可以选择一个叶子节点

v

，将

v

到根的简单路径中的一条边删掉，再在

v

与根之间连一条边，问最终树的直径最长为多少。

分析

一开始本人考虑每个子树内的最长链，最后找到根节点的两个最大子树求和，但是两条链可能在同一个子树内，这也是这道题的难点。

我们分步考虑：

不做操作：答案是树的直径。
只进行 $1$ 次操作：选一条从叶子出发的、不经过根节点的路径，删除路径上深度最小的点的父亲边，然后将其挂在根节点的下方。再选另一条从根节点出发的路径拼成答案（注意：两条路径不能相交，否则找不到合法的可以删除的边）。
进行 $2$ 次操作：等价于选择了两条不交的、且不经过根节点的路径分别挂在根节点下方，答案为选择的两条路径长度之和加上 $2$ 。
进行 $3$ 次及以上的操作是没有意义的，因为不可能存在一条路径同时覆盖了三条新增的边。
不做操作和只做一次操作的情况下，也可以认为是选择了两条不交且不经过根节点的路径。可以统一用树形 DP 来做。

目标

在以

u

为根的子树内，划分出两条没有交点的长链。

状态

d[u] 表示

u

子树中端点为

u

的最大链长。

f[u] 表示

u

子树中端点任意的最大链长。

g[u] 表示

u

子树中

2

条链的最大链长和，其中

1

条链端点为

u

。

h[u] 表示

u

子树中

2

条链的最大链长和，并且

2

条链端点任意。

D[u][3] 表示端点为儿子

v

的最大、次大、三大链长。

S[u][3] 表示对应的三个儿子的编号。

状态转移

$u$ 子树中端点为 $u$ 的最大链长：d[u]=max(d[u],d[v]+1)。
$u$ $u$ 子树中端点任意的最大链长：
1. 从 $v$ 子树继承：f[u]=max(f[u],f[v])。
2. 经过 $u$ 点：f[u]=max(f[u],D[u][0]+D[u][1]+2)。

$u$ $u$ 子树中最大链长和，其中一条端点为 $u$ $u$ ：
1. 从 $v$ 子树继承：g[u]=max(g[u],g[v]+1)。
2. 以 $u$ 为端点不过 $v$ 的最长链与 $v$ 中的任意最长链拼凑：g[u]=max(g[u],f[v]+(s[u][0]==v?D[u][1]:D[u][0])+1)。

$u$ $u$ 子树中最大链长和， $2$ $2$ 条链端点任意：
1. 从 $v$ 子树继承：h[u]=max(h[u],h[v])。
2. $2$ 条链来自不同子树：h[u]=max(h[u],f1+f2)。
3. $1$ 条来自 $v$ ， $1$ 条过 $u$ ：h[u]=max(h[u],f[v]+res+2)。
4. $1$ 条来自 $v$ ， $1$ 条过 $u,v$ ：h[u]=max(h[u],g[v]+(S[u][0]==v?D[u][1]:D[u][0])+2)。

由于链不能经过根节点 $1$ $1$ ，需要对根的每个子树分别讨论并计算答案，注意加上新建的两条边的贡献：
1. 子树之内的 $2$ 条链长和，用 h[i] 计算。
2. 子树之间的 $2$ 条链长和，用 f[i] 拼凑。

这道题也就迎刃而解了。

AC Code：

CPP

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const ll inf = 2e9, N = 200050, M = 2050, MOD = 1e9 + 7;

ll t, n, u, ans, mx1, mx2; 
ll d[N], f[N], g[N], h[N];
ll D[N][3], S[N][3];
vector<ll> e[N]; 

// 更新最大，次大，三大儿子 分类讨论 
void upd(ll x, ll y, ll dep){
	if(dep > D[x][0]){
		D[x][2] = D[x][1], S[x][2] = S[x][1];
		D[x][1] = D[x][0], S[x][1] = S[x][0];
		D[x][0] = dep, S[x][0] = y;
	}
	else if(dep > D[x][1]){
		D[x][2] = D[x][1], S[x][2] = S[x][1];
		D[x][1] = dep, S[x][1] = y;
	}
	else if(dep > D[x][2]) D[x][2] = dep, S[x][2] = y;
}

// 树形DP 
void dfs(ll now){
	ll f1 = 0, f2 = 0;
	for(ll i : e[now]){
		dfs(i);
		// 从v子树继承 
		d[now] = max(d[now], d[i] + 1);
		upd(now, i, d[i]);
		f[now] = max(f[now], f[i]);
		g[now] = max(g[now], g[i] + 1);
		h[now] = max(h[now], h[i]);
		// 保存两个最佳子树，便于更新h 
		if(f[i] > f1) f2 = f1, f1 = f[i];
		else if(f[i] > f2) f2 = f[i];
	}
	// 从两个最佳子树更新 
	f[now] = max(f[now], D[now][0] + D[now][1] + 2);
	h[now] = max(h[now], f1 + f2);
	// 子树遍历完后再更新 
	for(int i : e[now]){
		g[now] = max(g[now], f[i] + (S[now][0] == i ? D[now][1] : D[now][0]) + 1);
		ll res = 0, cnt = 0;
		if(S[now][0] != i) res += D[now][0], cnt ++;
		if(S[now][1] != i) res += D[now][1], cnt ++;
		if(cnt < 2 && S[now][2] != i) res += D[now][2];
		h[now] = max(h[now], f[i] + res + 2);
		h[now] = max(h[now], g[i] + (S[now][0] == i ? D[now][1] : D[now][0]) + 2);
	}
}

int main(){
	scanf("%lld", &t);
	while(t --){
		scanf("%lld", &n);
		// 记得全部清空！！！ 
		for(int i = 1; i <= n; i ++){
			e[i].clear();
			S[i][0] = S[i][1] = S[i][2] = f[i] = d[i] = h[i] = 0;
			D[i][0] = D[i][1] = D[i][2] = g[i] = -1;
		}
		for(int i = 2; i <= n; i ++){
			scanf("%lld", &u);
			e[u].push_back(i);
		}
		dfs(1);
		// 统计最大链，次大链之和与子树中的两大链的最大值作为答案 
		ans = 0; mx1 = -inf, mx2 = -inf;
		for(int i : e[1]){
			ans = max(ans, h[i] + 2);
			if(f[i] > mx1) mx2 = mx1, mx1 = f[i];
			else if(f[i] > mx2) mx2 = f[i];
		}
		if(n == 2) puts("1"); // 特判 
		else printf("%lld\n", max(ans, mx1 + mx2 + 2));
	}
	return 0;
}

题解：P10794 『SpOI - R1』架子鼓可以站 C

文章操作

题目大意

分析

目标

状态

状态转移

AC Code：

相关推荐

评论

题解：P10794 『SpOI - R1』架子鼓可以站 C