P14150 题解

· · 题解

思路

显然是树形 DP。

对一个节点 u 进行分析，显然它有 3 种情况：

那么对于当前节点 u，设其子树为 v_1,v_2,\ldots,v_s，那么子树同样也有 3 种情况。考虑如何转移。

以下令 S_0=\sum f_{v_i,0}，S_1\sum f_{v_i,1}，以及一个新的序列 B，使得 B_i=f_{v_i,2}-f_{i,1}，并将 B 从大往小排序。

状态 0：

由于父节点选，而当且当前节点不选，则需要从 v 中选取 k-1 个点。

显然，要贪心地选前 k-1 大的数，答案就是 S_1+\sum_{i=1}^{s-1}B_i。

状态 1：

和状态 0 同理，不过在 v 中选 k 个点，答案就是 S_1+\sum_{i=1}^sB_i。

状态 2：

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
int n,m,k,a[N],dp[N][3];
vector<int>e[N];
bool vis[N];
void dfs(int u,int fa){
    vis[u]=true;
    vector<int>vc;
    int sum0=0,sum1=0;
    for(auto v:e[u])
        if(v!=fa){
            dfs(v,u);
            sum0+=dp[v][0];
            sum1+=dp[v][1];
            vc.push_back(dp[v][2]-dp[v][1]);
        }
    sort(vc.begin(),vc.end(),greater<>());
    dp[u][0]=sum1;
    int cnt0=min(k-1,(int)vc.size());
    for(int i=0;i<cnt0;++i)
        if(vc[i]>0)
            dp[u][0]+=vc[i];
        else break;
    dp[u][1]=sum1;
    int cnt1=min(k,(int)vc.size());
    for(int i=0;i<cnt1;++i)
        if(vc[i]>0)
            dp[u][1]+=vc[i];
        else break;
    dp[u][2]=a[u]+sum0;
    return;
}
signed main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    while(m--){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        if(!vis[i]){
            dfs(i,0);
            ans+=max(dp[i][1],dp[i][2]);
        }
    printf("%lld\n",ans);
    return 0;
}