CodeForces 740D Alyona and a tree

倍增，延迟标记。

考虑一个$u$给他的哪几个祖先$v$贡献了$1$。越往上$dis(v,u)$越大，找到最远的一个还满足条件的$v$，$v$到$u$的父亲这条链上的答案都$+1$。延迟标记一下，然后从叶子节点往上走一遍求前缀和即可。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<ctime>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0);

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c = getchar();

    x = ;

    while(!isdigit(c)) c = getchar();

    while(isdigit(c))

    {

        x = x *  + c - '';

        c = getchar();

    }

}

int n;

long long a[];

int to[][];

long long len[][];

struct Edge

{

    int v;

    long long w;

}e[];

vector<int>G[];

int ans[];

int get(int x)

{

    long long L=;

    int res=x,y=x;

    while()

    {

        int flag=;

        for(int j=;j>=;j--)

        {

            if(len[res][j]==-) continue;

            if(len[res][j]+L>a[y]) continue;

            flag=; L=len[res][j]+L; res=to[res][j]; break;

        }

        if(flag==) break;

    }

    return res;

}

void dfs(int x,int fa,int idx,int dep)

{

    to[x][]=fa;

    if(idx!=-) len[x][]=e[idx].w;

    else len[x][]=-;

    for(int j=;j<=;j++)

    {

        if((<<j)>dep)

        {

            to[x][j]=-; len[x][j]=-;

            continue;

        }

        to[x][j]=to[to[x][j-]][j-];

        len[x][j]=len[x][j-]+len[to[x][j-]][j-];

    }

    int y=get(x);

    if(y!=x)

    {

        if(to[x][]!=-) ans[to[x][]]++;

        if(to[y][]!=-) ans[to[y][]]--;

    }

    for(int i=;i<G[x].size();i++)

    {

        int id=G[x][i];

        dfs(e[id].v,x,id,dep+);

    }

}

void F(int x)

{

    for(int i=;i<G[x].size();i++)

    {

        int id=G[x][i];

        F(e[id].v);

        ans[x]+=ans[e[id].v];

    }

}

int main()

{

    cin>>n;

    for(int i=;i<=n;i++) cin>>a[i];

    for(int i=;i<=n-;i++)

    {

        int fa; cin>>fa;

        e[i].v=i+; cin>>e[i].w;

        G[fa].push_back(i);

    }

    dfs(,-,-,);

    F();

    for(int i=;i<=n;i++) cout<<ans[i]<<" ";

    cout<<endl;

    return ;

}