CF 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`
简要做法
不难想到每个点暴力搜索祖先的做法
这样的话是`\mathcal{O}(n^2)`,明显过不去,考虑优化
想到树上搜索,不难想到倍增
于是我们便可以提前预处理好深度和倍增数组,每次倍增到能被控制的最远祖先
预处理`\mathcal{O}(n)`,每个点倍增`\mathcal{O}(\log(n))`
这里我们使用差分数组,每次维护一下`u`和`v`的值即可
单次修改`\mathcal{O}(1)`,最终再`\mathcal{O}(n)`前缀和一下差分数组即可得到答案
总时间复杂度`\mathcal{O}(n \log n)`
参考代码
#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;
}