思路

根据题目中的图示，我们不难推断出：假设有一条边连着 $u$ 和 $v$，那么右边的国家数就是以 $v$ 为根的子树的大小，左边的国家数就是总点数减去右边的国家数。

那么思路就很清晰了，存完边后我们dfs求出以每一个点为根的子树的大小，并计算一条边的费用，最后输出总费用即可。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,size[N],ans; // size[i]为以i为根子树的大小
struct edge{ // 边，x为边一端的点，len为边权
    ll x,len;
};
vector<edge> vec[N];
void dfs(ll x,ll fa){
    size[x]=1;
    for(auto i=vec[x].begin();i!=vec[x].end();i++)
        if((*i).x!=fa){
            dfs((*i).x,x);
            size[x]+=size[(*i).x];
            ans+=(*i).len*abs(n-size[(*i).x]*2);
            // 计算费用，绝对值内原为n-size[(*i).x]-size[(*i).x]，即左边国家数减右边国家数
        }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1,a,b,c;i<n;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        vec[a].push_back({b,c}),vec[b].push_back({a,c});
    }
    dfs(1,1);
    printf("%lld",ans);
    return 0;
}

dfs函数内对于vector元素的调用不要写成*i.x，因为*优先级很低，得加上括号，否则会报错。