过样例了,0分求助
查看原帖
过样例了,0分求助
385165
ZeroF楼主2023/7/11 16:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
	int to,next,dis;
}edge[1000010];
int head[500010],tot;
int a[500010],dep[500010];
int res=0;
void add(int u,int v,int dis){
	edge[++tot].to=v,edge[tot].dis=dis;
	edge[tot].next=head[u],head[u]=tot;
}
void dfs(int u,int fa){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to,dis=edge[i].dis;
		if(v==fa)continue;
		dfs(v,u);
		dep[u]=max(dep[u],dep[v]+dis);
	}
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to,dis=edge[i].dis;
		if(v==fa)continue;
		dfs(v,u);
		res+=dep[u]-dep[v]-dis;
	}
}
signed main(){
	int n,root;
	cin>>n>>root;
	for(int i=1;i<n;i++){
		int u,v,dis;
		cin>>u>>v>>dis;
		add(u,v,dis);
		add(v,u,dis);
	}
	dfs(root,-1);
	cout<<res<<endl;
	return 0;
}
2023/7/11 16:37
加载中...