医院设置（树的重心+树上dp）

先上复杂度的folyd解法，因为数据量小，可以过。但数据量大时就要树上dp了。（树上dp在后面）

#include <iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<vector>
#include<queue>
#include<utility>
#include<set>
using namespace std;
const int N = 1e3 + 10;
const long long INF = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int mp[N][N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)mp[i][j] = 0;
            else mp[i][j] = INF;

    for(int i=1;i<=n;i++)
    {
        int w, u, v;
        cin >> a[i] >> u >> v;
        if (u > 0)mp[i][u] =mp[u][i]= 1;
        if (v > 0)mp[i][v] = mp[v][i] = 1;
    }
    for (int k = 1; k<= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
     }
    int ans = INF;
    for (int i = 1; i <= n; i++)
    {
        int sum = 0;
        for (int j = 1; j <= n; j++)
        {
            sum += a[j] * mp[i][j];
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

树的重心+树上dp

引用大佬的讲解，tql 首先我们任意以一个点为根dfs一遍，求出以该点为根的总距离。方便起见，我们就以1为根。 接下来就是转移，对于每个u能达到的点v，有： f[v]=f[u]+size[1]-size[v]-size[v] 怎么来的呢？试想，当根从u变为v的时候，v的子树的所有节点原本的距离要到uu，现在只要到vv了，每个结点的距离都减少1，那么总距离就减少size[v]size[v]，同时，以v为根的子树以外的所有节点，原本只要到uu就行了，现在要到vv，每个节点的路程都增加了1，总路程就增加了size[1]-size[v]size[1]−size[v]，其中size[1]size[1]就是我们预处理出来的整棵树的大小，减去size[v]size[v]就是除以v为根的子树以外的结点数。

状态转移方程

f[v]=f[u]+size[1]−size[v]−size[v]

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define FAST ios::sync_with_stdio(false)
const int N = 1e5 + 10;
#define int long long
#define endl 

#define sc(n) scanf("%d",&n)
#define pr(n) printf("%d",n);
#define rep(i,n) for(int i=1;i<=n;++i)
#define per(i,n) for(int i=n-1;i>=1;--i)
const int INF = 0x3f3f3f3f;
using namespace std;
int e[N * 2], ne[N * 2], h[N],cnt;
bool st[N];
int w[N];
int f[N], sz[N];
//数组f[i]保存到f[i]处建医院的总距离
//数组sz[i]保存i所有子树的中人口数量
int ans = INF;
void add(int a, int b)
{
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void dfs(int u,int v,int dep)//预处理f[1]和sz数组
{
    sz[u] = w[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == v)continue;//可保证每个结点在dfs中只遍历一遍
        dfs(j, u, dep + 1);
        sz[u] += sz[j];
    }
    f[1] += w[u] * dep;
}
void dp(int u, int v)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == v)continue;
        f[j] = f[u] + sz[1] - 2 * sz[j];
        dp(j, u);
    }
    ans = min(ans, f[u]);
}
signed  main()
{
    FAST;
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    rep(i, n)
    {
        int a,b;
        cin >> w[i] >> a >> b;
        if(a)add(i, a),add(a,i);//没有负结点和0结点
        if(b)add(i, b),add(b,i);
    }
    dfs(1,0,0);
    dp(1, 0);
    cout << ans << endl;
    return 0;
}