Codeforces 740D(二分+树上差分)

Codeforces 740D
题意:给出一棵有根树,树上每个点、每条边都有一个权值。现在给出“控制”的定义:对一个点$u$,设点$v$在其子树上,则称$u$控制$v$。要求求出每个点控制了多少个点

我们从根向下 DFS。对于一个点,他上面距离他点权长的点都是控制这个点的。只要找到这个临界点即可。由于树边权为正,所以边权前缀和为单调序列,用二分找。用倍增也行。然后这一段就+1,树上差分即可。

知识点:
1、一定要在纸上写思路!不管多简单的题目,只要是这种 50 行以上的
2、不要看错题目!仔细看,有必要将简要题意写下来!
3、正数前缀和-单调性-二分

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 200000 + 5;
LL n, a[MAXN], c[MAXN], cf[MAXN], fa[MAXN];
vector<LL> G[MAXN];
vector<pair<LL, LL > > dis;
inline void ins(LL x, LL y) {G[x].push_back(y);}
void dfs1(LL u, LL pa, LL cst) {
cf[u]++;
fa[u] = pa; LL tmp = cst - a[u];
vector<pair<LL, LL > >::iterator it = lower_bound(dis.begin(), dis.end(), make_pair(tmp, 0ll));
LL p = it - dis.begin(); p--;
if (p >= 0ll) cf[dis[p].second]--;
dis.push_back(make_pair(cst, u));
for (LL i = 0ll; i < (LL)G[u].size(); i++) {
LL v = G[u][i];
if (v != pa) dfs1(v, u, cst + c[v]);
}
dis.pop_back();
}
void dfs2(LL u, LL pa) {
for (LL i = 0ll; i < (LL)G[u].size(); i++) {
LL v = G[u][i];
if (v != pa) dfs2(v, u), cf[u] += cf[v];
}
}
void clean() {
ms(cf, 0);
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (LL p, w, i = 2; i <= n; i++) scanf("%lld%lld", &p, &w), ins(p, i), c[i] = w;
dfs1(1, 0, 0);
dfs2(1, 0);
for (LL i = 1; i <= n; i++) printf("%lld ", cf[i] - 1);
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}

------ 本文结束 ------