Title Link: https://codeforces.com/contest/739/problem/B

Main idea of the title:

Given a tree, if V is the child node of u and dis (U, V) < = a [v], it is called u and can be controlled to v

Output the number of nodes that each node can control

Topic idea:

After reading the question, first deduce the formula:

Assuming that V is the child of u, dis(u,v) can be expressed as: deep[v] - deep[u], and deep is the weighted depth

So from deep[v] - deep [u] < = a [v], then for any point u, find out how many nodes in the subtree meet, and deep [u] < = deep[v] - a [v]

Idea 1:

Tree section + chairman tree is OK

The chairman tree takes deep[u] - a[v] as the insertion point. In this case, an offset base needs to be added

The code will not be released. Just set the chairman tree template

Complexity: About O(n*50)

Idea 2:

dsu on a tree

Obviously, this is a problem of static subtree information statistics. For a subtree, you can count all the information of deep[v]-a[v]. Finally, you can query how many are less than or equal to deep[u]

Originally written code, with unordered_map maintains a tree array

Complexity: O(n*logn*logn*C) C is unordered_ Constant of map

Sure enough, TLE37

At this time, in order to reduce C and the second log, it is discretized to control the complexity to nlog^2

1060ms

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int sz[maxn],son[maxn];
ll a[maxn],num[maxn],deep[maxn];
vector<pair<int,ll>>v[maxn];
ll sum[maxn];
vector<ll>g;
int nn;
ll nmax = 0,base = 0;
void dfs(int u,int fa,ll w){
    sz[u] = 1;
    deep[u] = deep[fa] + w;
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        dfs(e,u,x.second);
        sz[u] += sz[e];
        if(sz[son[u]]<sz[e]) son[u] = e;
    }
}
int getid(ll x){
    return lower_bound(g.begin(),g.end(),x) - g.begin() + 1;
}
ll GetSum(ll pos){
    ll ans = 0;
    while(pos){
        ans += sum[pos];
        pos -= pos&-pos;
    }return ans;
}
void Modify(ll pos,int w){
    while(pos <= nn){
        sum[pos] += w;
        pos += pos&-pos;
    }
}
void cal(int u,int fa,int f){
    Modify(getid(deep[u]-num[u]),f);
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        cal(e,fa,f);
    }
}
void solve(int u,int fa,int del){
    for(auto x:v[u]){
        int e = x.first;
        if(e == son[u]) continue;
        solve(e,u,1);
    }
    if(son[u]) solve(son[u],u,0);
    for(auto x:v[u]){
        int e = x.first;
        if(e == son[u]) continue;
        cal(e,u,1);
    }
    a[u] = GetSum(getid(deep[u]));
    Modify(getid(deep[u]-num[u]),1);
    if(del) cal(u,fa,-1);
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(num[i]);
    for(int i=2;i<=n;i++){
        ll x,y;read(x);read(y);
        v[x].push_back({i,y});
    }
    dfs(1,1,0);

    for(int i=1;i<=n;i++){
        g.push_back(deep[i] - num[i]);
        g.push_back(deep[i]);
    }
    sort(g.begin(),g.end());
    g.erase((unique(g.begin(),g.end())),g.end());
    nn = g.size();

    solve(1,1,0);
    for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    return 0;
}
/***
5 5 3
1 2 3 4 5
3 3
3 2
1 5
***/

Idea 3:

Consider a node that can be controlled to be his father node

Then you can find the node x that finally meets one condition in the path from this point to the root node, and then make a difference in the tree

As for how to find this x node, you can consider doubling to ensure that this node is found within the complexity of the log

Finally, dfs traversal can be restored

560ms

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
vector<pair<int,ll>>v[maxn];
int f[maxn][23];
ll sum[maxn][23];
ll res[maxn],a[maxn],num[maxn];
void dfs(int u,int fa,ll w){
    if(u != fa){
        f[u][0] = fa;
        sum[u][0] = w;
        for(int i=1;i<=20;i++){
            f[u][i] = f[f[u][i-1]][i-1];
            sum[u][i] = sum[u][i-1] + sum[f[u][i-1]][i-1];
        }
        ll  p = u,temp = num[u];
        for(int i=20;i>=0;i--){
            if(f[p][i] && sum[p][i] <= temp){
                temp -= sum[p][i];
                p = f[p][i];
            }
        }
        res[f[p][0]]--;
        res[f[u][0]]++;
    }
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        dfs(e,u,x.second);
    }
}
ll ans = 0;
void work(int u,int fa){
    a[u] += res[u];
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        work(e,u);
        a[u] += a[e];
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(num[i]);
    for(int i=2;i<=n;i++){
        ll x,y;read(x);read(y);
        v[x].push_back({i,y});
    }
    dfs(1,1,0);
    work(1,1);
    for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    return 0;
}
/***
5 5 3
1 2 3 4 5
3 3
3 2
1 5
***/

Idea 4:

The third way of thinking can be optimized without doubling. Because the depth is absolutely increasing, it can be divided into two points

After the node is found, the difference is performed again

As for how to split, just look at the code

It has to be Du Jiao

365ms

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
vector<pair<int,ll>>v[maxn];
int f[maxn][23];
ll d[maxn];
ll res[maxn],a[maxn];
int sta[maxn];
ll num[maxn];
void dfs(int u,int fa,ll w,int deep){
    sta[deep] = u;d[deep] = w;
    int l = lower_bound(d+1,d+1+deep,w-num[u]) - d - 1;
    res[sta[l]]--;res[u]++;
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        dfs(e,u,w+x.second,deep+1);
    }
}
ll ans = 0;
void work(int u,int fa){
    a[u] += res[u];
    for(auto x:v[u]){
        int e = x.first;
        if(e == fa) continue;
        work(e,u);
        a[u] += a[e];
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(num[i]);
    for(int i=2;i<=n;i++){
        ll x,y;read(x);read(y);
        v[x].push_back({i,y});
    }
    dfs(1,1,0,1);
    work(1,1);
    for(int i=1;i<=n;i++) printf("%lld ",a[i]-1);
    return 0;
}
/***
5 5 3
1 2 3 4 5
3 3
3 2
1 5
***/