大佬求助玄关86分WA
查看原帖
大佬求助玄关86分WA
1020566
prg_equal_depressed楼主2024/7/19 14:31
#include <iostream>
#define _int long long
using namespace std;
_int n,m,x1,x2,x3,l[500005],r[500005],q1[500005],q2[500005],sd[500005],cnt,s;
void create(_int x,_int y,_int z){
	q1[++cnt]=y;q2[cnt]=z;
	r[cnt]=l[x];l[x]=cnt;
} 
void dfs(_int x,_int d){
	for (_int i=l[x];i;i=r[i]){
		if (q1[i]==d) continue;
		dfs(q1[i],x);
		sd[x]=max(sd[x],sd[q1[i]]+q2[i]);
	}
	for (_int i=l[x];i;i=r[i]){
		if (q1[i]==d) continue;
		s+=sd[x]-(sd[q1[i]]+q2[i]);
	}
}
int main(){
	cin>>n>>m;
	for (_int i=1;i<n;i++){
		cin>>x1>>x2>>x3;
		create(x1,x2,x3);
		create(x2,x1,x3);
	}
	dfs(m,0);
	cout<<s;
	return 0;
}
2024/7/19 14:31
加载中...