全RE 求助!
查看原帖
全RE 求助!
177540
Mr_steamedbread楼主2020/10/24 09:24
#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
long long n,s,a,b,t,u,ans;
struct node
{
	long long to,cost;
};
node temp;
vector<node>g[maxn*2];
long long dp[maxn*2];
long long read()
{
	long long x=1,f=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9')
	{
		if(c='-') x=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		f*=10;
		f+=c-'0';
		c=getchar();
	}
	return x*f;
	
}
void dfs(int cur)
{
	for(register int i=0;i<g[cur].size();i++)
	{
		dfs(g[cur][i].to);
		dp[cur]=max(dp[cur],dp[g[cur][i].to]+g[cur][i].cost);
	}
	for(register int i=0;i<g[cur].size();i++)
	{
		ans+=dp[cur]-dp[g[cur][i].to]-g[cur][i].cost;
	}
}
int main()
{
	n=read();
	s=read();
	for(register int i=1;i<n;i++)
	{
		a=read(),b=read(),t=read();
		temp.to=b,temp.cost=t;
		g[a].push_back(temp);
	}
	dfs(s);
	printf("%lld",ans);
}
2020/10/24 09:24
加载中...