ABC368G

zibenlun · 2024-09-01 15:48:29 · 题解

思路

首先思考 Takahashi 如何让自己走过的路径最小。根据题意，一定要从 1 号点出发并回到 1 号点，所以每一个点到 1 号点之间的边一定是要经过两次的。

知道了计算经过所有点的路径长度的方法之后，就可以根据其特点发现，当选取部分点的时候，选子节点一定比选择他的祖先更优。因为选取子节点后，同样会经过其祖先，所以说选择一个点就相当于选择了其祖先。现在我们只需要统计所有的叶子的权值（到达此处的路径长度和）。此时我们会发现有多个儿子的点会导致路径长度的重复计算，我们需要将有多个儿子的节点的权值转移给它其中的一个儿子。因为选取点的时候是按照路径最长的方式选取，所以每一次都是要选取能使路径增加最长的点，所以我们选择将每个点的权值传递给他的重儿子。之后统计所有的叶子的权值，输出即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
struct nd{int y,z;};
int s[N],dp[N],n,ans;
priority_queue<int> q;
vector<nd> v[N];
void dfs(int x,int fa){//找重儿子
    int maxx=0;
    for(auto i:v[x]){
        if(i.y==fa) continue;
        dp[i.y]=i.z;
        dfs(i.y,x);
        if(dp[i.y]>maxx)maxx=dp[i.y],s[x]=i.y;
    }
    dp[x]+=maxx;
}
void dfss(int x,int fa){//计算所有点的权值
    for(auto i:v[x]){
        if(i.y==fa) continue;
        if(s[x]==i.y)dp[i.y]=dp[x]+i.z;
        else dp[i.y]=i.z;
        //转移给重儿子
        dfss(i.y,x);
    }if(v[x].size()==1&&fa!=0)q.push(dp[x]);
    //存下叶子
}
signed main() {
    cin>>n;
    for(int i=1,x,y,z;i<n;i++) {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs(1,0);dp[1]=0;dfss(1,0);
    //dp数组用了两次
    //在dfs中用于统计重儿子
    //在dfss中用于存储当前点的权值
    for(int i=1;i<=n;i++){
        if(q.size()) ans+=q.top()*2,q.pop();
        //在所有为选取的叶子中选择最大的
        //选完所有的叶子后，其他的点不在会对答案产生贡献
        cout<<ans<<"\n";
    }
    return 0;
}