Alyona and a tree 树上差分 +倍增

112 阅读 0 评论 74 点赞

我是靠谱客的博主自由睫毛，这篇文章主要介绍Alyona and a tree 树上差分 +倍增，现在分享给大家，希望可以做个参考。

传送门

题目描述

给定一颗树，每个结点有对应点权，每条边也有对应边权。如果dis<v, u> <= val[u]，则说明结点u被结点v所管辖。对于每个结点，输出它管辖的结点数目。

分析

这道题如果我们遍历每一个点并且往上爬，把所有可以被控制的点的答案++，那么大概率是要被t的，所以我们可以去用一种更为巧妙的做法：树上差分

首先我们用倍增去维护维护这颗树上距离这个点1 << i远的点，这样就可以求出某个点所能控制的最远的点是谁，然后用树上差分，就可以构造差分数组，最后往后传递即可

代码

复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10,M = N * 2;
int h[N],ne[M],e[M],idx;
ll w[N];
int n;
ll d[N];
int a[N];
int ans[N];
int f[N][21];
int num;

void add(int x,int y,int z){
    ne[idx] = h[x],e[idx] = y,w[idx] = z,h[x] = idx++;
}

void dfs(int u){
    for(int i = 1;i <= 20;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    int back = u;
    for(int i = 20;~i;i--){
        if(f[back][i] && d[u] - d[f[back][i]] <= a[u])
            back = f[back][i];
    }
    ans[f[back][0]]--;
    ans[f[u][0]]++;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        f[j][0] = u;
        d[j] = d[u] + w[i];
        dfs(j);
        ans[u] += ans[j];
    }
}

int main(){
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 2;i <= n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,i,y);
    }
    dfs(1);
    for(int i = 1;i <= n;i++) printf("%d ",ans[i]);
    return 0;
}

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/

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
81
82
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10,M = N * 2;
int h[N],ne[M],e[M],idx;
ll w[N];
int n;
ll d[N];
int a[N];
int ans[N];
int f[N][21];
int num;

void add(int x,int y,int z){
    ne[idx] = h[x],e[idx] = y,w[idx] = z,h[x] = idx++;
}

void dfs(int u){
    for(int i = 1;i <= 20;i++) f[u][i] = f[f[u][i - 1]][i - 1];
    int back = u;
    for(int i = 20;~i;i--){
        if(f[back][i] && d[u] - d[f[back][i]] <= a[u])
            back = f[back][i];
    }
    ans[f[back][0]]--;
    ans[f[u][0]]++;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        f[j][0] = u;
        d[j] = d[u] + w[i];
        dfs(j);
        ans[u] += ans[j];
    }
}

int main(){
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 2;i <= n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,i,y);
    }
    dfs(1);
    for(int i = 1;i <= n;i++) printf("%d ",ans[i]);
    return 0;
}

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/