自动搬运

查看原文

来自洛谷，原作者为

	leozhao123 不是这咕值要多久才能掉到 0 啊

搬运于2025-08-24 23:16:35，当前版本为作者最后更新于2025-06-06 22:09:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

传送门 | AC 记录

这篇题解部分受 taoyiwei17_cfynry@loj.ac 的启发，在此处膜拜 %%% ！

---

以下约定：

• 以 $0$ 号节点为根；
• 定义一个图的权值为它的点权和最大的连通子图的点权和；
• 定义节点 $u$ 的向上子树为原树中删去 $u$ 的子树后构成的连通图；
• 记 $son_u$ 为节点 $u$ 的子节点集合，$c_u$ 为节点 $u$ 的点权。

考虑树形 DP。

记 $f_u,g_u$ 分别为节点 $u$ 的子树中包括 $\textit{\textbf{u}}$ 和不包括 $\textit{\textbf{u}}$ 的权值最大的连通图的权值，$F_u$ 为 $u$ 的子树的权值。则易得 $f$ 的转移：

$$f_u=c_u+\sum_{v\in son_u}\max(0,f_v)$$

然后考虑 $g$ 的转移。假设现在已经得到了 $\set{F_v|v\in son_u}$，由于各个子树间不连通，且要求的 $g_u$ 不包含节点 $u$，所以：

$$g_u=\max_{v\in son_u}\set{F_v}$$

特别地，当节点 $u$ 为叶子即 $son_u=\varnothing$ 时 $g_u=-\infty$。然后有：

$$F_u=\max(f_u,g_u)$$

接下来考虑如何得到答案。题目要求 “$E$ 中没有连接 $V_a$ 中节点和 $V_b$ 中节点的边”，也就是从 $T_a$ 到 $T_b$ 至少经过 $1$ 个不属于 $V_a$ 和 $V_b$ 的节点。而对于一个节点 $u$，若将 $u$ 和所有与 $u$ 相连的边都删去，则整棵树会裂成多个连通图，其中任意 $2$ 个连通图或它的子图在原树中均满足这个条件。

更进一步，删去节点 $u$ 分裂出的图可分为两种：

1. 原树中 $u$ 的子节点的子树；
2. 原树中 $u$ 的向上子树。

第一种的权值就是上文求的 $F$。第二种的权值求法与上文相似，具体地，记 $f'_u,g'_u$ 分别为节点 $u$ 的向上子树中包括 $u$ 和不包括 $u$ 的权值最大的连通图的权值，$F'_u$ 为 $u$ 的向上子树的权值，则对于 $v\in son_u$ 有：

$$\begin{aligned} f'_v &= f_u-\max(0,f_v)+\max(0,f'_u)\\ g'_v &= \max\set{f'_u,g'_u,\set{F_w|w\in son_u\land v\ne w}}\\ F'_v &= \max(f'_v,g'_v)\\ \end{aligned} $$

枚举每个 $u\in V$，求 $\set{F'_u,\set{F_v|v\in son_u}}$ 中的最大值与次大值之和，对这个值在取最大值即为答案。

---

枚举每个点是 $\mathcal{O}(n)$，在 DFS 里排序均摊 $\mathcal{O}(n\log n)$，所以时间复杂度 $\mathcal{O}(n\log n)$。排序还可以用打擂台代替，优化到 $\mathcal{O}(n)$，但我懒得写了。

代码：

// -std=c++17 -O2
// By leozhao123
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const ll N=5e5+3;
ll n,c[N],F[N],f[N],g[N],ans=-1e18;
vector<ll>G[N];
void dfs1(ll u,ll fa) {// 计算出 f,g,F 数组
	f[u]=c[u];
	g[u]=-1e18;
	for(auto v:G[u]) {
		if(v==fa) continue;
		dfs1(v,u);
		f[u]+=max(0LL,f[v]);
		g[u]=max(g[u],F[v]);
	}
	F[u]=max(f[u],g[u]);
}
void dfs2(ll u,ll fa,ll _f,ll _g) {// _f,_g 即文中的 f'_u,g'_u
	vector<ll>P,Q;
// P 为向上、向下两部分的权值
// Q 为向下部分的权值
	for(auto v:G[u]) {
		if(v==fa) continue;
		P.push_back(F[v]);
		Q.push_back(F[v]);
	}
	P.push_back(max(_f,_g));// max(_f,_g) 即 F'_u
	while(P.size()<2) P.push_back(-1e18);
	while(Q.size()<2) Q.push_back(-1e18);
// 上面 2 行不写将导致 UB 或 RE
	sort(P.begin(),P.end());
	sort(Q.begin(),Q.end());
	ans=max(ans,P[P.size()-1]+P[P.size()-2]);// 用最大值与次大值的和更新 ans
	for(auto v:G[u]) {
		if(v==fa) continue;
		ll tmp1=f[u]-max(0LL,f[v])+max(0LL,_f);// 下传的 f'_v 值
		ll tmp2;// 下传的 g'_v 值
		if(Q[Q.size()-1]==F[v]) tmp2=Q[Q.size()-2];// 如果最大值是 v 本身，就取次大值
		else tmp2=Q[Q.size()-1];// 否则取最大值
		dfs2(v,u,tmp1,max(tmp2,max(_f,_g)));
	}
}
ll findSum(int _N,vector<int>C,vector<int>U,vector<int>V) {
    n=_N,c[n-1]=C[n-1];
    for(ll i=0;i<n-1;++i) {
        c[i]=C[i];
        G[U[i]].push_back(V[i]);
        G[V[i]].push_back(U[i]);
    }
    dfs1(0,-1);
    dfs2(0,-1,-1e18,-1e18);
    return ans;
}