社区讨论

为啥是40?

P2052[NOI2011] 道路修建参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7xjkfo
此快照首次捕获于
2025/11/21 05:14
4 个月前
此快照最后确认于
2025/11/21 05:14
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
	char c;
	int sign=1;
	while((c=getchar())<'0'||c>'9') if(c=='-') sign=-1;
	int res=c-'0';
	while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+(c^48);
	return res*sign;
}
int n,head[1000005],cnt,x,y,z,num[1000005];
struct Edge{
	int to,next,w;
}edge[2000005];
long long ans;
void add_edge(int from,int to,int dis)
{
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	edge[cnt].w=dis;
	head[from]=cnt;
}
void dfs(int fa,int x)
{
	num[x]=1;
	for(int i=head[x];i;i=edge[i].next)
	{
		if(edge[i].to!=fa)
		{
			dfs(x,edge[i].to);
			ans+=(long long)(abs(n-2*num[edge[i].to])*edge[i].w);
			num[x]+=num[edge[i].to];
		}
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n-1;i++)
	{
		x=read(),y=read(),z=read();
		add_edge(x,y,z);add_edge(y,x,z);
	}
	dfs(1,1);
	printf("%lld\n",ans);
	return 0;
} 

回复

2 条回复,欢迎继续交流。

正在加载回复...