HZOJ-257：树的颜色

大家好，欢迎来到IT知识分享网。

 题目描述

​ 有一棵树，它的所有节点都需要染色，每个节点都有一个代价基础值 Ci。第一个染色的是根节点，其余节点染色的时候其父节点必须已染色。染色一个节点会用掉一个时间单位，每个节点染色的代价是染完此节点时的总时间 T 乘上这个节点的基础值 Ci。求染完所有节点所需的最小代价。

输入

​ 第一行包含两个整数 N,R其中，N是树中节点个数，R是根节点编号。

​ 第二行输入 N个整数，编号为 i的节点的代价基础值 Ci。（1≤Ci≤500）

​ 接下来 N−1行为边的信息，每行两个数分别表示父节点编号和子节点编号。

输出

​ 输出一个整数，表示最小代价。

样例输入

5 1 1 2 1 2 4 1 2 1 3 2 4 3 5

样例输出

33

#include <iostream> #include <vector> #include <string> #include <set> #include <stack> #include <deque> #include <cmath> #include <algorithm> using namespace std; #define MAX_N 1000 int C[MAX_N + 5] = { 0 }; int fa[MAX_N + 5] = { 0 }; int vis[MAX_N + 5] = { 0 }; int cnt[MAX_N + 5] = { 0 }; double w[MAX_N + 5] = { 0 }; int n, r; long long ans = 0; int find_x() { int x = -1; for (int i = 1; i <= n; i++) { if (i == r || vis[i] == 1) continue; if (x == -1 || w[x] < w[i]) x = i; } return x; } int find_fa(int x) { if (vis[fa[x]] == 1) return find_fa(fa[x]); return fa[x]; } int main() { cin >> n >> r; for (int i = 1; i <= n; i++) { cin >> C[i]; ans += C[i]; fa[i] = i; w[i] = C[i]; cnt[i] = 1; } for (int i = 1, a, b; i < n; i++) { cin >> a >> b; fa[b] = a; } for (int i = 1; i < n; i++) { int x = find_x(); int fa_x = find_fa(x); ans += cnt[fa_x] * C[x]; C[fa_x] += C[x]; cnt[fa_x] += cnt[x]; w[fa_x] = 1.0 * C[fa_x] / cnt[fa_x]; vis[x] = 1; } cout << ans; return 0; }