AC（树的思路）

看到题目就知道城市之间的连接方式恰好为无根树，我们假设1为根，则样例可以构建为如下的树

那么对于一条边 E(a,b），我们设 a 为深度更大的节点，size_i 为以 i 为根的子树的大小，则 a 一侧的城市数量为 size_a，另一侧就是 size_1-size_a，于是城市数量差就是 |size_1-2size_a|。

上面的式子 size_i 显然可以用 dfs 预处理得到，那么就有如下代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N=1e6+10;

typedef pair<int,pair<int,int>> PII;

int n;
int siz[N],father[N];
int h[N],e[N<<1],ne[N<<1],idx;
PII r[N];

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
	idx++;
	return;
}

int dfs(int x,int fa)
{
	if(x==-1)
		return 0;
	father[x]=fa;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa)
			continue;
		siz[x]+=dfs(j,x);
	}
	return siz[x];
}

int main()
{
	memset(h,-1,sizeof(h));
	cin>>n;
	for(int i=1;i<=n;i++)
		siz[i]=1;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		r[i]={a,{b,c}};
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	int root=1;
	long long res=0;
	for(int i=1;i<n;i++)
	{
		int a=r[i].first,b=r[i].second.first,c=r[i].second.second;
		if(siz[a]>siz[b])
			swap(a,b);
		res+=c*abs(siz[root]-2*siz[a]);
	}
	cout<<res<<endl;
	return 0;
}