题目链接

题目描述

给定一棵节点数为`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;
}