题面

解题思路

方法很多，比如左偏树、主席树、树上查分 看到数据结构大佬瑟瑟发抖

这里提供一种新的算法 $\large \to$ 树状数组+离散化（并不用记录 $dfs$ 序

分析

求子树中到根的距离在一定范围内的点，可以对每棵子树用树状数组维护一个所有点到根的距离，查询时查询一定范围即可

但是明显这是不行的，空间和时间都不允许

考虑一下优化，绝对距离是没必要的，可以有相对距离来表示两点间的情况（也就是说，我们只需要知道两者的大小关系），因此可以预处理出每个点到 $root$ 的距离，排序后维护其离散值即可，查询时也可以用离散值来代替

再考虑对每个点维护子树信息的优化，不难发现，$dfs$ 实现时，对于一个点，$dfs$ 其子树前 和 完成后，对答案造成的影响只有子树里的信息，因此可以只开一个树状数组维护信息，每次记录 $dfs$ 前后的结果，两者之差即为答案

实现过程

1、先 $dfs$ 跑一遍，预处理出所有点到 $root(1)$ 的 $dis$ 值，用 $p$ 数组记录

2、将 $p$ 数组按升序排序

3、再次 $dfs$，用树状数组 $f$ 记录各点到 $root$ 距离的离散值，每次在访问一个节点的儿子前，查询该点能到最远距离的离散值，然后在树状数组中标记这个点的 $dis$，遍历子树，最后再次查询，两次查询之差即为该点的答案，因为只对该点子树进行的操作，不会产生额外的影响

cur=lower_bound(p+1,p+t+1,dis[k])-p;//当前点的离散值
pos=lower_bound(p+cur,p+t+1,dis[k]+R)-p;//最远能到的点的离散值
if(p[pos]>dis[k]+R) --pos;//要求 小于等于
res=Query(pos),Modify(cur);//先查询，再修改
. . .
Ans[k]=Query(pos)-res;//再次查询，记录两次查询的差为答案

warning

1、记得开 $long\ long $

2、$1$ 到 $root$ 的 $dis$ 值，虽然是 $0$ 也要记录，否则会影响上述过程中 $cur$ 的值，间接影响答案，如下图情况，若题目中的 $L<10$ 则 $root$ 的答案会少 $1$ ，当然，也可以通过特判解决

Code

#include<bits/stdc++.h>
#define rgt register
#define LL long long
#define N 200003
using namespace std;
struct Edge{
    int to,nxt;
    LL dis;
    Edge(int a,int b,LL c):to(a),nxt(b),dis(c){}
    Edge(){}
}b[N];//记录边
int head[N],n,t;
int f[N],Ans[N];
LL dis[N],p[N],R;
inline LL read() {
    rgt LL s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rgt int x,rgt int y) {
    b[++t]=Edge(y,head[x],read()),head[x]=t;
}
inline void built(rgt int k) {//预处理dis
    p[++t]=dis[k];//1到root的距离也要加入
    rgt int i,to;
    for(i=head[k];i;i=b[i].nxt) {
        to=b[i].to,
        dis[to]=dis[k]+b[i].dis;
        built(to);
    }
}
inline int Query(rgt int x) {
    int res=0;
    for(;x;x-=x&(-x)) res+=f[x];
    return res;
}
inline void Modify(rgt int x) {
    for(;x<=t;x+=x&(-x)) ++f[x];
}
inline void solve(rgt int k) {
    rgt int i,to,cur,res,pos;
    cur=lower_bound(p+1,p+t+1,dis[k])-p;
    pos=lower_bound(p+cur,p+t+1,dis[k]+R)-p;//假装从cur开始查能省点时间
    if(p[pos]>dis[k]+R) --pos;
    res=Query(pos),Modify(cur);
    for(i=head[k];i;i=b[i].nxt)
        to=b[i].to,solve(to);
    Ans[k]=Query(pos)-res;
}
int main()
{
    int i;
    n=read(),R=read();//n点数，R距离
    for(i=2;i<=n;i++) add(read(),i);
    t=0,built(1),//第一遍dfs
    sort(p+1,p+t+1),solve(1);//第二遍dfs得出结果
    for(i=1;i<=n;i++) printf("%d\n",Ans[i]);
    return 0;
}

最后

如果题目没有 子树中的限制…

devil.