「Codeforces 739B」Alyona and a tree - 倍增 + 差分

给定一棵节点数为`n`的树

这棵树的根节点为`1`

这棵树有点权`val_i`和边权`dis_i`

定义`dist(u,v)`为从`u`到`v`的简单路径上的边权和

顶点`u`控制顶点`v`,当且仅当`v`在`u`的子树中且`dist(u,v) \le val_v`

求每个顶点`u`能控制几个顶点

`1 \le n \le 2 \times 10^5`

链接

「Codeforces 739B」

题解

不难想到每个点暴力搜索祖先的做法

这样的话是`\mathcal{O}(n^2)`,明显过不去,考虑优化

想到树上搜索,不难想到倍增

于是我们便可以提前预处理好深度和倍增数组,每次倍增到能被控制的最远祖先

预处理`\mathcal{O}(n)`,每个点倍增`\mathcal{O}(\log(n))`

这里我们使用差分数组,每次维护一下`u`和`v`的值即可

单次修改`\mathcal{O}(1)`,最终再`\mathcal{O}(n)`前缀和一下差分数组即可得到答案

总时间复杂度`\mathcal{O}(n \log n)`

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>

const int N = 2e5 + 5;
const int M = 4e5 + 5;
const int LOGN = 20;

int n, num_edge, head[N];
int ans[N], fa[LOGN + 5][N], val[N];
long long depth[N];

struct Node
{
int next, to, dist;
} edge[M];

void add_edge(int u, int v, int dist)
{
edge[++num_edge].next = head[u];
edge[num_edge].to = v;
edge[num_edge].dist = dist;
head[u] = num_edge;
}

void dfs_1(int u)
{
//第1个dfs预处理深度和倍增
for (int i = 1; i <= LOGN; ++i)
fa[i][u] = fa[i - 1][fa[i - 1][u]];
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
int dist = edge[i].dist;
fa[0][v] = u;
depth[v] = depth[u] + dist;
dfs_1(v);
}
}

void solve(int u)
{
int x = u;
for (int i = LOGN; i >= 0; i--)
if (fa[i][x] and depth[u] - depth[fa[i][x]] <= val[u])
x = fa[i][x];
if (x != 1)
ans[fa[0][x]]--;
if (u != 1)
ans[fa[0][u]]++;
}

void dfs_2(int u)
{
//第2个dfs前缀和差分数组
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
dfs_2(v);
ans[u] += ans[v];
}
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
for (int i = 2; i <= n; i++)
{
int u, dist;
scanf("%d%d", &u, &dist);
add_edge(u, i, dist);
}
dfs_1(1);
for (int i = 1; i <= n; i++)
solve(i);
dfs_2(1);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×