http://www.lydsy.com/JudgeOnline/problem.php?id=3011

题意

给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于L的点有多少个。

题解

dfs，对于每个点，打一个+1的标记，在从它到根的路径上，第一个大于>L的点打一个-1的标记，

则每个点的答案就是以它为根的子树的标记和。

官方题解写的倍增，我只会记录dfs序列，然后二分。

#include<cstring>
#include<cmath>
#include<climits>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=210000;
int v[N],next[N],head[N],n,k; ll len,w[N];
int f[N],stack[N],tot;ll s[N];
void build(int x,int y,ll z)
{
    v[++k]=y;w[k]=z;next[k]=head[x];head[x]=k;
}
 
int check(int r)
{
    ll l=1;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(s[stack[tot]]-s[stack[mid]]>len) l=mid;
        else r=mid-1;
    }
    return stack[l];
}
 
void dfs(int x,ll sum)
{
    stack[++tot]=x;s[x]=sum;
    f[x]+=1;f[check(tot)]-=1;
    for(ll i=head[x];i;i=next[i])
    {
        dfs(v[i],sum+w[i]);
        f[x]+=f[v[i]];
    }
    tot--;
}
 
int main()
{
    scanf("%d%lld",&n,&len);
    for(int i=2;i<=n;i++)
    {
        ll x,y;scanf("%d%lld",&x,&y);
        build(x,i,y);
    }
    s[0]=-ll(1e20);stack[++tot]=0;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",f[i]);
}