社区讨论
为啥是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 条回复,欢迎继续交流。
正在加载回复...