题解：P12582 「KTSC 2019 R1」树

leozhao123 · 2025-06-06 22:09:17 · 题解

传送门 | AC 记录

这篇题解部分受 [email protected] 的启发，在此处膜拜 %%% ！

以下约定：

• 以 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 的转移：

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

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

接下来考虑如何得到答案。题目要求 “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 有：

枚举每个 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;
}