题意
给出以1号点为根的一棵有根树,问每个点的子树中与它距离小于等于l的点有多少个
题解
似乎有好多种做法啊……然而蒟蒻只会打打主席树的板子……
调了一个上午一直WA……狠下心来重打一遍居然直接一遍过……
先dfs一遍，把到根节点的距离算出来，然后建出树上的主席树
然后考虑，$d[v]-d[u]<=L$，$d[v]<=L+d[u]$
然后就是对于每一个$d[u]+L$查询一下区间内有多少比它小的就好
细节问题：因为不能保证$d[u]+L$在离散化后的数组内存在，所以要用upper_bound，并查询比它小的，而且要在离散化的数组后面加一个inf
//minamoto
#include<bits/stdc++.h>
#define N 200005
#define M 4000005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline ll read(){
#define num ch-'0'
char ch;bool flag=;ll res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char obuf[<<],*o=obuf;
void print(int x){
if(x>) print(x/);
*o++=x%+;
}
int sum[M],L[M],R[M],rt[N];
int ver[N<<],Next[N<<],head[N];ll edge[N<<];
int ls[N],rs[N];ll a[N],b[N];
int n,m,cnt,tot;ll p;
void update(int last,int &now,int l,int r,int x){
sum[now=++cnt]=sum[last]+;
if(l==r) return;
int mid=(l+r)>>;
if(x<=mid) R[now]=R[last],update(L[last],L[now],l,mid,x);
else L[now]=L[last],update(R[last],R[now],mid+,r,x);
}
int query(int u,int v,int l,int r,int k){
if(r<k) return sum[v]-sum[u];
if(l>=k) return ;
int mid=(l+r)>>;
if(k<=mid) return query(L[u],L[v],l,mid,k);
else return query(R[u],R[v],mid+,r,k)+sum[L[v]]-sum[L[u]];
}
inline void add(int u,int v,ll e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
}
void dfs(int u,int fa,ll d){
b[ls[u]=++m]=d,a[m]=d;
for(int i=head[u];i;i=Next[i])
if(ver[i]!=fa) dfs(ver[i],u,d+edge[i]);
rs[u]=m;
}
int main(){
n=read(),p=read();
for(int u=;u<=n;++u){
int v=read();ll e=read();
add(v,u,e);
}
dfs(,,);
sort(b+,b++m);
m=unique(b+,b++m)-b-;
for(int i=;i<=n;++i){
int k=lower_bound(b+,b++m,a[i])-b;
update(rt[i-],rt[i],,m,k);
}
b[m+]=inf;
for(int i=;i<=n;++i){
int k=upper_bound(b+,b++m,a[ls[i]]+p)-b;
k=query(rt[ls[i]-],rt[rs[i]],,m,k);
print(k);
*o++='\n';
}
fwrite(obuf,o-obuf,,stdout);
return ;
}