E63 树形DP P1131 [ZJOI2007] 时态同步

// 树形DP O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=500010;
int n,s;
long long ans,dis[N];
int head[N],to[N<<1],ne[N<<1],w[N<<1],idx;
void add(int x,int y,int z){
  to[++idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx;
} 

void dfs(int x,int fa){
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(y==fa) continue;
    dfs(y,x);
    dis[x]=max(dis[x],dis[y]+w[i]);
  }
  
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(y==fa) continue;
    ans+=dis[x]-(dis[y]+w[i]);
  }
}
int main(){
  scanf("%d%d",&n,&s);
  for(int i=1,x,y,z;i<n;i++){
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);add(y,x,z);
  }
  dfs(s,0);
  printf("%lld",ans);
}

/*
n - 1 条边，是一棵树。
考虑一颗 x 为头的子树，如果想让这棵树的所有结束节点加 n，
可以直接到 x 头上的边加 n，这样代价最小且合法。
考虑树形 dp，自底而上递归，不断用最大时间更新。  
*/ 
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

struct node {
	int x;
	LL w;
};

vector<node> G[N];
int S; LL ans;

LL dfs(int x, int fa, LL sum) {   // 当前节点，父亲节点，到当前节点的代价 
	LL mx = 0;    // 最大时间 
	int siz = 0;   // 当前 x 的分支个数 
	for (node i : G[x]) if (i.x != fa) {
		int y = i.x; LL w = i.w;
		
		LL t = dfs(y, x, sum + w);
		if (t < mx) {      // 如果 y 的代价比 x 之前分支的代价小 
			ans += (mx - t);    // 改变 x 到 y 这条边的代价 
		}
		else if(mx != 0 && mx < t) {   // 如果之前有分支， y 的代价之前分支的代价小 
			ans += siz * (t - mx);     // 之前分支的每条边都得改变 
		}
		mx = max(mx, t);     // 更新最大值 
		siz ++;       // 增加分支个数 
	}
	
	if (G[x].size() == 1) {   // 结束节点（只有与父亲节点的一条边） 
		return sum;
	}
	
	return mx; 
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	cin >> S;
	for (int i = 1; i < n; i ++) {
		int x, y; LL w;
		cin >> x >> y >> w;
		G[x].push_back({y, w});
		G[y].push_back({x, w});
	}
	
	ans = 0;
	dfs(S, 0, 0);
	cout << ans << "\n";
	
	return 0;
}