萌新泪如雨下,跪地拜求大佬观瞧代码
查看原帖
萌新泪如雨下,跪地拜求大佬观瞧代码
289056
北射天狼楼主2023/5/15 18:04

有点不理解为什么把 calcal 和 dfsdfs 合并起来能AC(如注释),但是分开写的时候就错呢?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n;
ll size[N];
ll head[N],cnt = 0;
struct node{
	int v,next,w;
}tree[N<<1];
ll ans = 0;
void add(int u,int v,int w)
{
	tree[++cnt].next = head[u];
	tree[cnt].v = v;
	tree[cnt].w = w;
	head[u] = cnt;
}
void dfs(int u,int father)
{
	for (int i=head[u];i;i=tree[i].next){
		int v = tree[i].v;
		if (v == father)
		    continue;
		dfs(v,u);
		size[u] += size[v];
	//ans += (ll)abs(size[v]*2 - n) * tree[i].w;
	}
	size[u]++;
}
void cal(int u,int father)
{
	for (int i=head[u];i;i=tree[i].next){
		int v = tree[i].v;
		if (v == father)
		    continue;
		long long sum = abs(n - size[v] - size[v]);
		ans += (long long)tree[i].w * sum;
	}
}
signed main()
{
	scanf("%d",&n);
	for (int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,-1);
	cal(1,-1);
	printf("%lld\n",ans);
    return 0;
}
2023/5/15 18:04
加载中...