医院设置

题目

链接 ：https://www.luogu.com.cn/problem/P1364

题解

#include <stdio.h>

using namespace std;

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

#define min(a, b) ({\
    (a) < (b) ? (a) : (b);\
})

//dis[u]: 表示以u为根的总距离
int n, w[101], size[101];
int ans, dis[101];
bool fa[101];
int to[201], head[101], ne[201], cnt = 1; // 链式前向星 

void add_edge(int a, int b) {
    to[cnt] = b;
    ne[cnt] = head[a];
    head[a] = cnt++;
}
//求以每个节点为根节点挂的节点个数，包括自身 
int dfs(const int& u, const int& f, const int& hight) {
    //fa[u] = f;
    size[u] = w[u]; //w[i]存储i号节点自身节点数量 
    for (int i = head[u]; i; i = ne[i]) {
        if (to[i] == f) continue; //下一个点不是父节点
        size[u] += dfs(to[i], u, hight + 1);
    }
    //自底而上求得所以节点到1号节点的距离 
    dis[1] += w[u] * hight; //表示以1为根的总距离，先预处理求得以1为根，f[1]的值
    return size[u];
}

void dp(const int& u, const int& f) { // 树型dp 
    
    for (int i = head[u]; i; i = ne[i]) {
        if (to[i] == f) continue;
        dis[to[i]] = dis[u] + size[1] - size[to[i]] * 2;
        dp(to[i], u);
    }
    ans = min(ans, dis[u]);
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d %d %d", &w[i], &a, &b);
        if (a) add_edge(i, a), add_edge(a, i);
        if (b) add_edge(i, b), add_edge(b, i);
    }
    dfs(1, 0, 0); //以1为根节点，求以每个节点为根节点的树的大小 
    ans = 0x7fffffff;
    dp(1, 0);
    printf("%d\n", ans);
    return 0;
}