题解：P12710 [KOI 2021 Round 1] 两个团队

sLMxf · 2025-08-13 20:38:53 · 题解

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

P12710 [KOI 2021 Round 1] 两个团队

简述题意

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

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

请输出最大的权值之和。

算法分析

显然的树形 DP。

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

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

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

• 当 f_v> 0 时：
• 否则：

然后这道题做完了。

时间复杂度 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;
}

:::