自动搬运

查看原文

来自洛谷，原作者为

	sLMxf 史莱姆先锋or死了吗小枫？/总会有... /机房风气蒸蒸日上/小号:crz_qwq&deadX

搬运于2025-08-24 23:17:37，当前版本为作者最后更新于2025-08-13 20:38:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这不是奶龙都会的题目吗。

P12710 [KOI 2021 Round 1] 两个团队

简述题意

请选择两个连通块，连通块需要满足：

• 一定在一颗子树内，且根必须选择。
• 是联通块。（？）
• 连通块权值之和需要尽量大。
• 任意一个点不能两个联通块中。

请输出最大的权值之和。

算法分析

显然的树形 DP。

一颗子树内的答案，要么是选择根往下的一个连通块和一个不与上述连通块相交的连通块，要么选择两棵子树的最优。

维护这些值。定义 $maxk$ 表示连通块中最大的一块连通块（符合上述定义，下同），$f$ 表示选根的最优解，$g$ 表示不选根且不被 $f$ 所在连通块包含的连通块。那么这颗子树的答案为：

$$\max\{f_i+g_i,maxk_{v_1}+maxk_{v_2}\}\{v_1,v_2\in son_x,v1\ne v2\} $$

那么不难得到三个东西的转移：

• 当 $f_v> 0$ 时：
  • $f_x\gets f_x+f_v$。
  • $g_x\gets \max(g_x,g_v)$。
• 否则：
  • $f_x\gets f_x$。
  • $g_x\gets \max(g_x,maxk_v)$。
• $maxk_x=\max(f_x,maxk_v)(v\in son_x)$。

然后这道题做完了。

时间复杂度 $O(n)$。

代码实现

:::success[AC code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=100000000000000000;
int w[200005],max_k[200005],f[200005],g[200005],ans=-inf;
vector<int>G[200005];
void dfs(int x)
{
	int maxx=-inf,cmax=-inf;
	g[x]=max_k[x]=-inf;f[x]=w[x];
	for(auto v:G[x])
	{
		dfs(v);
		if(f[v]>0) f[x]+=f[v],g[x]=max(g[x],g[v]);
		else g[x]=max(g[x],max_k[v]);
		max_k[x]=max(max_k[x],max_k[v]);
		if(max_k[v]>=maxx) cmax=maxx,maxx=max_k[v];
		else if(max_k[v]>=cmax) cmax=max_k[v];
	}
	max_k[x]=max(max_k[x],f[x]);
	ans=max(ans,max(g[x]+f[x],maxx+cmax));
}
signed main()
{
	int n,fa;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>fa;
		if(i!=1) G[fa].push_back(i);
	}
	dfs(1);
	cout<<ans;
	return 0;
}

:::