题解 | #点权#
牛牛排队
https://ac.nowcoder.com/acm/contest/11183/A
//对于每个节点来说它的最小消费肯定是以他文根节点, 所有子节点传递过来的最小的两个; 如果每个节点都跑一遍树形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;
}