无向图邻接表方式：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; 
    cin >> n;
    
    vector<int> populations(n+1, 0);
    vector<int> leftChild(n+1, 0);
    vector<int> rightChild(n+1, 0);

    // 读入数据
    for (int i = 1; i <= n; i++) {
        cin >> populations[i] >> leftChild[i] >> rightChild[i];
    }

    // 构建无向图邻接表
    // 虽然是二叉树，但我们可以看做是无向图，以便后续的 BFS
    vector<vector<int>> adj(n+1);
    for (int i = 1; i <= n; i++) {
        if (leftChild[i] != 0) {
            adj[i].push_back(leftChild[i]);
            adj[leftChild[i]].push_back(i);
        }
        if (rightChild[i] != 0) {
            adj[i].push_back(rightChild[i]);
            adj[rightChild[i]].push_back(i);
        }
    }

    // 对每个节点执行 BFS，计算距离和
    int minDistanceSum = INT_MAX;

    for (int start = 1; start <= n; start++) {
        // BFS 计算 start 到所有其他节点的距离
        vector<int> dist(n+1, -1);
        dist[start] = 0;
        queue<int> q;
        q.push(start);

        while(!q.empty()) {
            int u = q.front(); q.pop();
            for (int nxt : adj[u]) {
                if (dist[nxt] == -1) {
                    dist[nxt] = dist[u] + 1;
                    q.push(nxt);
                }
            }
        }

        // 计算距离和
        int distanceSum = 0;
        for (int i = 1; i <= n; i++) {
            distanceSum += populations[i] * dist[i];
        }

        minDistanceSum = min(minDistanceSum, distanceSum);
    }

    cout << minDistanceSum << "\n";

    return 0;
}

//方法2：找树的重心，换根DP法

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10001;

struct Edge {
    int next, to;
} e[MAXN << 1];

int head[MAXN], num, w[MAXN], n, size[MAXN];
long long ans = MAXN, f[MAXN];

inline void add(int from, int to) {
    e[++num].to = to;
    e[num].next = head[from];
    head[from] = num;
}

void dfs(int u, int fa, int dep) {  //预处理f[1]和size
    size[u] = w[u];
    for (int i = head[u]; i; i = e[i].next) {
        if (e[i].to != fa) {
            dfs(e[i].to, u, dep + 1);
            size[u] += size[e[i].to];
        }
    }
    f[1] += w[u] * dep;
}

void dp(int u, int fa) {  //转移
    for (int i = head[u]; i; i = e[i].next)
        if (e[i].to != fa) {
            f[e[i].to] = f[u] + size[1] - size[e[i].to] * 2;
            dp(e[i].to, u);
        }
    ans = min(ans, f[u]);  //取最小值
}
int a, b;
int main() {
    ans *= ans;
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> w[i];
        cin >> a >> b;
        if (a) add(i, a), add(a, i);
        if (b) add(i, b), add(b, i);
    }
    dfs(1, 0, 0);
    dp(1, 0);
    printf("%lld\n", ans);
    return 0;
}