题解 | #点权#

//对于每个节点来说它的最小消费肯定是以他文根节点， 所有子节点传递过来的最小的两个； 如果每个节点都跑一遍树形dp是O（n方）会t；

我们先固定一个根节点跑一遍dfs，确定它的最小消费； 然后对于剩下的节点，他们的消费已经是除根结点外的所有子节点的最小消费，因此，我们只是需要判断根节点更新它需要的消费会不会更小，如果会就更新； 不可能存在子节点用本身的消费+边权去更新父节点， 然后换根dp后父亲节点又更新子节点;因为大小关系. 其实某一点一定是从子节点或者父亲结点更新过来的，这点也能看出是换根法

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e6+5;
int last[N],tot;
int dp[N],d[N],n,f[N][2];

struct Node{
	int w,to,next;
}a[N];


void add(int u,int v,int w){
	tot++;
	a[tot].w = w;
	a[tot].to = v;
	a[tot].next = last[u];
	last[u] = tot;
}

void dfs(int u,int fa){
	for(int i = last[u];i>=0;i = a[i].next){
		int v = a[i].to;
		int w = a[i].w;
		if(v==fa) continue;
		if(d[v]==1){
			dp[v] = 0 ;
		}else{
			dfs(v,u);
		}
		if(dp[v]+w<f[u][0]){
			f[u][1] = f[u][0];
			f[u][0] = w+dp[v];
		}else if(dp[v]+w<f[u][1]){
			f[u][1] = dp[v]+w;
		}
		if(f[u][1]+f[u][0]<dp[u]){
			dp[u] = f[u][1]+f[u][0];
		}
	}
}


void dfs1(int u,int fa){
	for(int i = last[u];i>=0;i = a[i].next){
		int v = a[i].to;
		int w = a[i].w;
		if(v==fa) continue;
		if(d[v]==1){
			dp[v] = 0;
			continue;
		}
		if(dp[u]+w<f[v][0]){
			f[v][1] = f[v][0];
			f[v][0] = w+dp[u];
		}else if(w+dp[u]<f[v][1]){
			f[v][1] = w+dp[u];
		}
		if(f[v][1]+f[v][0]<dp[v]){
			dp[v] = f[v][1]+f[v][0];
		}
		dfs1(v,u);
	}
}

int main(){
	int u,v,w;
	cin>>n;
	memset(last,-1,sizeof(last));
	memset(dp,INF,sizeof(dp));
	memset(f,INF,sizeof(f));
	tot = -1;
	for(int i = 1;i<=n-1;i++){
		cin>>u>>v>>w;
		add(u,v,w);//前西星存边
		add(v,u,w);
		d[u]++;
		d[v]++;//记录入度
	}
	
	int root;
	for(int i = 1;i<=n;i++){
		if(d[i]>1){
			root = i;
			break;
		}
	}
	dfs(root,0);//第一次树形dp
	
	dfs1(root,0);//换根dp
	if(n==1){
		cout<<"0"<<endl;
		return 0;
	}
	for(int i =1;i<=n;i++){
		if(dp[i]>=INF) cout<<-1<<" ";
		else cout<<dp[i]<<" ";
	}
	
	return 0;
}