BZOJ-3011: [Usaco2012 Dec]Running Away From the Barn

Description

给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于l的点有多少个。【对于不同的节点，l是相同的】n<=200000

考虑节点对于祖先的贡献。一个点会使其到前l-1个祖先答案+1。倍增找祖先后差分即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,fa[201000][20],ans[201000];
ll deep[201000],len;
int head[201000],to[201000],nxt[201000],cnt;
ll f[201000];
inline void add(int x,int y,ll z)
{
    to[++cnt]=y; nxt[cnt]=head[x];
    head[x]=cnt; f[cnt]=z;
}
void dfs1(int x)
{
    for(int i=head[x];i;i=nxt[i]) 
    {
        fa[to[i]][0]=x;
        deep[to[i]]=deep[x]+f[i];
        dfs1(to[i]);
    }
}
void dfs2(int x)
{
    for(int i=head[x];i;i=nxt[i])
    {
        dfs2(to[i]);
        ans[x]+=ans[to[i]];
    }
}
int main()
{
    scanf("%d%lld",&n,&len);
    int x; ll z;
    for(int i=2;i<=n;++i)
    {
        scanf("%d%lld",&x,&z);
        add(x,i,z);
    }
    dfs1(1);
    for(int i=1;i<=18;++i)
        for(int j=1;j<=n;++j)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    for(int i=1;i<=n;++i)
    {
        x=i; ans[i]++;
        for(int j=18;~j;--j) if(deep[i]-deep[fa[x][j]]<=len) x=fa[x][j];
        ans[fa[x][0]]--;
    }
    dfs2(1);
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}