提交寄录

#include<iostream>
#include<algorithm>
const int sz=1e5+10;
int n,l,w;
struct BIT{
    long long arr[sz];
    int lowbit(int x){
        return x&-x;
    }
    void add(int p,int x){
        for(int i=p;i<=n;i+=lowbit(i))arr[i]+=x;
    }
    long long query(int p){
        if(p<=0)return 0;
        long long res=0;
        for(int i=p;i;i-=lowbit(i))res+=arr[i];
        return res;
    }
}bit;
struct edge{
    int nxt,to,w;
}graph[sz<<1];
int head[sz],hpp;
void addEdge(int from,int to,int w){
    graph[++hpp]=edge{head[from],to,w};
    head[from]=hpp;
}
int size[sz],max[sz],rt;
bool vis[sz];
void dfs(int u,int fau,int psz){
    size[u]=1,max[u]=0;
    for(int p=head[u];p;p=graph[p].nxt){
        int v=graph[p].to;
        if(vis[v]||v==fau)continue;
        dfs(v,u,psz);
        max[u]=std::max(max[u],size[v]);
        size[u]+=size[v];
    }
    max[u]=std::max(max[u],psz-size[u]);
    if(max[u]<max[rt])rt=u;
}
struct ver{
    int dep,dis;
    bool operator<(const ver &a)const{
        return dis<a.dis;
    }
};
ver qq[sz];
int tail;
void dist(int u,int fau,int dis,int dep){
    qq[++tail]=ver{dep,dis},size[u]=1;
    for(int p=head[u];p;p=graph[p].nxt){
        int v=graph[p].to;
        if(vis[v]||v==fau)continue;
        dist(v,u,dis+graph[p].w,dep+1);
        size[u]+=size[v];
    }
}
long long count(int u,int dis,int dep){
    long long res=0;
    tail=0;
    dist(u,0,dis,dep);
    std::sort(qq+1,qq+tail+1);
    for(int i=1;i<=tail;i++)bit.add(qq[i].dep+1,1);
    for(int i=1,j=tail;i<=j;i++){
        while(i<j&&qq[i].dis+qq[j].dis>w)bit.add(qq[j].dep+1,-1),j--;
        bit.add(qq[i].dep+1,-1);
        res+=bit.query(l-qq[i].dep+1);
    }
    return res;
}
long long ans=0;
void solve(int u){
    vis[u]=true;
    ans+=count(u,0,0);
    for(int p=head[u];p;p=graph[p].nxt){
        int v=graph[p].to;
        if(vis[v])continue;
        ans-=count(v,graph[p].w,1);
        rt=0,dfs(v,0,size[v]),solve(rt);
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>l>>w;
    for(int i=2,f,w;i<=n;i++)
        std::cin>>f>>w,addEdge(i,f,w),addEdge(f,i,w);
    max[0]=1e9,dfs(1,0,n),solve(rt);
    std::cout<<ans<<"\n";
    return 0;
}