题目描述
https://codeforces.com/contest/1436/problem/D
Solution
注意到每个点的居民只能向子树走，所以我们考虑以子树来划分阶段
对于一棵树，如果它能够平分，那么答案一定是 $\lceil \frac{sz_u}{leaf_u}\rceil $
如果不能平分，那么一定说明有一个子树的居民太多导致不需要向他分配，这时候我们可以递归处理
感觉好像还是有点抽象，留坑吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 200010
#define ll long long
using namespace std;
int n, a[maxn];
struct Edge {
int to, next;
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
ll ans; ll sum[maxn], leaf[maxn];
void dfs(int u) {
int F = 1; sum[u] = a[u];
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; F = 0;
dfs(v); sum[u] += sum[v]; leaf[u] += leaf[v];
}
leaf[u] += F; ans = max(ans, sum[u] / leaf[u] + (sum[u] % leaf[u] != 0));
}
int main() { memset(head, -1, sizeof head);
cin >> n;
for (int i = 2; i <= n; ++i) {
int x; scanf("%d", &x);
add_edge(x, i);
}
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
dfs(1); cout << ans << endl;
return 0;
}
|