求调
查看原帖
求调
935837
1073741824aa楼主2025/2/1 13:22
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int nxt,v,w;
}e[9999999];
int dp1[5000001],dp2[5000001],head[5000001],n,rt,u,v,w;
void solve(int x,int fa){
//	if(head[x]==1&&x!=rt)return;
	int qwq=0,wqw=0;
	for(int i=head[x];i;i=e[i].nxt){
		if(e[i].v==fa)continue;
		solve(e[i].v,x);
		qwq++;
		dp2[x]+=dp2[e[i].v];
		dp1[x]=max(dp1[x],dp1[e[i].v]+e[i].w);
		wqw+=dp1[e[i].v]+e[i].w;
	}
	dp2[x]+=qwq*dp1[x]-wqw;
}
main(){
//	freopen("P1131_1.in","r",stdin);
//	freopen("P1131_1.out","w",stdout);
	cin>>n>>rt;
	for(int i=1;i<n;i++){
		cin>>u>>v>>w;
		e[2*i-1].nxt=head[u];
		e[2*i-1].v=v;
		e[2*i-1].w=w;
		head[u]=2*i-1;
		e[2*i].nxt=head[v];
		e[2*i].v=u;
		e[2*i-1].w=w;
		head[v]=2*i;
	}
	solve(rt,0);
	cout<<dp2[rt];
}全部WA了
2025/2/1 13:22
加载中...