本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}