题解：P10974 Accumulation Degree

· · 题解

这个题不是特别难，就是细节有亿点多。本人将尽量详细讲解。

思路

怎么想到换根？

我们这么定义 A(x)：

树的累积度是指其节点中最大累积度的值。你的任务是找到给定树的累积度（摘自题面）。

这里重写了一篇。

所有的终端节点只能是根节点和叶子节点（这个是因为只有这些点有可能度为一）。

当一个节点作为答案时，考虑它和它子节点的答案差别。

它子节点和它子节点的子树内终端的最大容量一定大于等于它对它子节点子树内终端的最大容量。显然，可能中间这条边撑不住那么大贡献。而对于子树外的终端节点就一定大于等于它子节点对于子树外终端节点的贡献。

我们发现这题的瓶颈就是父节点和子节点的这条边。

这条边选中点从上到下（从父到子），会使父节点的除自己子树内的所有贡献与边权取较小值。从子到父会时自己子树内节点的最大贡献和与边权取较小值。

我们钦定顺序为从父到子（毕竟根节点知道），对于根及所有节点子树内的答案我们可以算出来，在父亲节点考虑，对于儿子节点，可以将自己的贡献剪掉子节点子树内贡献与连边取较小值（其实就是实际贡献啦），得到儿子子树之外的节点实际贡献和，这个子树外节点的贡献的所有点对于子节点来说都会经过父子之间的这条边（毕竟这个父节点是它到每个终端节点最近公共祖先路径上的必经节点），所以会取较小值（画个图会好理解得多），那么可以列出式子。

设 u,v 表示父与子节点，数组 size 表示子节点子树内的贡献。可列式子 dp[v]=min(dp[u]-min(size[v],edge[i]),edge[i])+size[v]。

第一项即子节点对于子树之外的贡献，第二项是子树内的贡献。

由于我们从上到下遍历的，所以子节点处理之前父节点一定被处理好了，而 size 我们早都预处理好了。

到此，我们写成了一个换根。

现在可以写代码了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+50,M=2e6+50;
#define ll long long
ll size[N],dp[N];
ll edge[M];
int ver[M],head[N],Next[M],tot,son[N];
void add(int x,int y,ll z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=z,Next[tot]=head[y],head[y]=tot;
}
int n,t;
void dfs1(int x,int fa){
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
        if(son[y]>1)size[x]+=min(edge[i],size[y]);
        else size[x]+=edge[i];
    }
}
void dfs2(int x,int fa){
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(son[x]==1)dp[y]=size[y]+edge[i];
        else if(son[y]>1)dp[y]=min(dp[x]-min(size[y],edge[i]),edge[i])+size[y];
        else dp[y]=min(dp[x]-edge[i],edge[i])+size[y];
        dfs2(y,x);
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        tot=0;
        for(int i=1;i<=n;i++)head[i]=0,size[i]=0,dp[i]=0,son[i]=0;
        for(int i=1;i<n;i++){
            int x,y;
            ll z;
            scanf("%d%d%lld",&x,&y,&z);
            son[x]++,son[y]++;
            add(x,y,z);
        }
        dfs1(1,0);
        dp[1]=size[1];
        dfs2(1,0);
        ll maxn=dp[1];
        for(int i=2;i<=n;i++){
            maxn=max(maxn,dp[i]);
        }
        printf("%lld\n",maxn);
    }
    return 0;
}