记录编号	347720	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007]时态同步	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	4.125 s
提交时间	2016-11-13 15:43:53	内存使用	17.51 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ll long long 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=501000;
struct edge{int to,next,dis;}e[maxn*2];
int tot,head[maxn];
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].next=head[u];
	head[u]=tot;
}
int n,rt;
int f[maxn],g[maxn];
ll ans;
void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(to==fa) continue;
		dfs(to,u);
		f[u]=max(f[u],f[to]+e[i].dis);
	}
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(to==fa) continue;
		ans+=f[u]-f[to]-e[i].dis;
	}
}
int main(){
	freopen("synch.in","r",stdin);freopen("synch.out","w",stdout);
	int __size__=50<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	n=read(),rt=read();
	for(int i=1;i<n;i++){
		int a=read(),b=read(),c=read();
		add(a,b,c);add(b,a,c);
	}
	dfs(rt,0);
	printf("%lld\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}