算法1

(暴力DFS) $O(n^2)$

枚举每个点作为医院然后暴力DFS计算所有居民到医院的路程之和，每次DFS是求以当前节点为起点，其他所有点到起点的距离乘上该节点的居民数然后求和。

时间复杂度

共有n个点，枚举每个点需要$O(n)$的复杂度，总复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, INF = 1e9;

int h[N], ne[2 * N], e[2 * N], idx;
int A[N];

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

int n;

int dfs(int u, int t, int father) {
    int res = A[u] * t;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        res += dfs(j, t + 1, u);
    }
    return res;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        A[i] = a;
        if (b) add(i, b), add(b, i);
        if (c) add(i, c), add(c, i);
    }

    int res = INF;
    for (int i = 1; i <= n; i++) {
        res = min(res, dfs(i, 0, 0));
    }
    cout << res << endl;

    return 0;
}

算法2

(换根法+树形DP) $O(n)$

本质上是两次DP。先用一次DFS求出将医院设在该节点时，所有子节点的居民到医院的路程之和(注意并不是所有节点的居民，只是以当前节点为根的子树的居民距离之和)，以及当前子树的居民数量之和存储在cnt中。这样根节点的结果就是我们的初始答案。

然后从树根开始再进行一次DFS枚举医院的位置并求所有居民的路程之和，每次当医院从当前节点向子节点i移动时，以子节点i为根的居民到医院的距离会减少1，共减少cnt[i]，其他节点的居民到医院的距离会增加1，共增加sum - cnt[i]，这里sum是居民数量之和，因此总路程增加的量为sum - 2 * cnt[i]，遍历完所有的节点并取最小值就是答案。

时间复杂度

两次DFS的时间复杂度都为$O(n)$，因此总复杂度也为$O(n)$

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 220, INF = 1e9;

int h[N], e[M], ne[M], idx;
int cnt[N];
int sum, res;

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

int dfs1(int u, int father) {
    int t = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        t += dfs1(j, u) + cnt[j];
        cnt[u] += cnt[j];
    }
    return t;
}

void dfs2(int u, int father, int cur) {
    res = min(res, cur);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        dfs2(j, u, cur + sum - 2 * cnt[j]);
    }
}

int main() {
    int n;
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int c, l, r;
        cin >> c >> l >> r;
        cnt[i] = c;
        sum += c;
        if (l) add(i, l);
        if (r) add(i, r);
    }

    res = dfs1(1, -1);
    dfs2(1, -1, res);

    cout << res << endl;

    return 0;
}