P1131 时态同步

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000001;
int N,S;
long long maxn[MAXN];
int to[MAXN];int ll;
int hea[MAXN];
int nex[MAXN];
long long Val[MAXN];
long long f[MAXN];
void bl(int u,int v,long long val){
	to[++ll]=v;nex[ll]=hea[u];hea[u]=ll;Val[ll]=val;
}
void dfs(int u,int fa){
	for(int i=hea[u];i;i=nex[i]){
		int v=to[i];if(v==fa)continue;
		dfs(v,u);
		maxn[u]=max(maxn[u],maxn[v]+Val[i]);
	}
	for(int i=hea[u];i;i=nex[i]){
		int v=to[i];if(v==fa)continue;
		f[u]+=maxn[u]-maxn[v]-Val[i]+f[v];
	}
}
int main(){
	scanf("%d%d",&N,&S);
	for(int i=1;i<N;i++){
		int u,v;long long val;
		scanf("%d%d%lld",&u,&v,&val);
		bl(u,v,val);bl(v,u,val);
	}
	dfs(S,0);
	printf("%lld",f[S]);
}