Alyona and a tree (树上倍增+差分)

116 阅读 0 评论 77 点赞

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

题意： 来源（洛谷翻译
在这里插入图片描述
题解:
首先先转化一下问题，题目问当前结点（u）的子树中有多少个孩子（设为v）满足dis(u,v)<=a[v]，那么我们可以统计每个结点分别对哪些结点做出了贡献。
首先考虑暴力的解法，枚举每个点，针对于每一个结点，不断的去往上找他的父亲结点，并且在找的过程中给每个结点+1的权值，直到找到的结点跟当前结点的距离大于当前结点为止。这样的时间复杂度最差是n^2。
我们发现一步一步的往上找，显然很暴力，对于这种题目，我们可以用类似于二分的方法去查找，那也就是倍增了，显然我们可以快速找到那个临界的结点，但是他们之间的该如何标记呢，我们用差分给他打两个标记即可！
然后最后遍历一遍树处理一下差分即可。

代码:

复制代码

#pragma GCC optimize(3 , "Ofast" , "inline")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl 'n'
const int maxn = 6e5+10;
int mod=1e9+7;

int n;
int a[maxn];
vector<pair<int,int> > edge[maxn];

int dep[maxn],dis[maxn];
int f[maxn][25];
void dfs(int x,int w,int fa){
    f[x][0]=fa;
    dep[x]=dep[x]+1;
    dis[x]=dis[fa]+w;
    for(int i=1;i<=20;i++){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(auto i:edge[x]){
        dfs(i.first,i.second,x);
    }
}
int b[maxn];

void sol(int now){
    int x=now;
    for(int i=20;i>=0;i--){
        if(f[x][i]&&dis[now]-dis[f[x][i]]<=a[now]){
            x=f[x][i];
        }
    }
    b[f[x][0]]--;
    b[f[now][0]]++;
}

void DFS(int x){
    for(auto i:edge[x]){
        DFS(i.first);
        b[x]+=b[i.first];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back({i,y});
    }
    dfs(1,0,0);
    for(int i=2;i<=n;i++){
        sol(i);
    }
    DFS(1);
    for(int i=1;i<=n;i++){
        cout<<b[i]<<" ";
    }
}

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
#pragma GCC optimize(3 , "Ofast" , "inline")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl 'n'
const int maxn = 6e5+10;
int mod=1e9+7;

int n;
int a[maxn];
vector<pair<int,int> > edge[maxn];

int dep[maxn],dis[maxn];
int f[maxn][25];
void dfs(int x,int w,int fa){
    f[x][0]=fa;
    dep[x]=dep[x]+1;
    dis[x]=dis[fa]+w;
    for(int i=1;i<=20;i++){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(auto i:edge[x]){
        dfs(i.first,i.second,x);
    }
}
int b[maxn];

void sol(int now){
    int x=now;
    for(int i=20;i>=0;i--){
        if(f[x][i]&&dis[now]-dis[f[x][i]]<=a[now]){
            x=f[x][i];
        }
    }
    b[f[x][0]]--;
    b[f[now][0]]++;
}

void DFS(int x){
    for(auto i:edge[x]){
        DFS(i.first);
        b[x]+=b[i.first];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back({i,y});
    }
    dfs(1,0,0);
    for(int i=2;i<=n;i++){
        sol(i);
    }
    DFS(1);
    for(int i=1;i<=n;i++){
        cout<<b[i]<<" ";
    }
}