首先感谢TheOnlyMan为我们带来主席树的精彩讲解，

但说到底不管在不在线，本题只用普通的线段树就够了。

时间空间都更优秀。AC结果：287ms 42300KB

思路

先跑一个dfs（因为最近写惯了所以树链剖分没改回来），然后把树拍平去建线段树。 我们知道以x为根的子树表示的范围就是[dfn[x]+1,dfn[x]+sz[x]-1]，+1是因为不需要考虑根节点， 那么我们判断这个范围里面有多少个dis[p]-dis[x]>=k的点，然后把这个dis[p]累加起来即可， 如果有n个合适的点，那么我们就要减去n个dis[x]，因此，我们需要维护的信息为每个节点的距离和、距离最大值和距离最小值。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;

struct E{
	int v,w,nxt;
}e[N<<2];

int head[N],cnt=0;
void addedge(int u,int v,int w){
	e[++cnt]=(E){v,w,head[u]};head[u]=cnt;
	e[++cnt]=(E){u,w,head[v]};head[v]=cnt;
}

int sz[N],fa[N],dis[N],dep[N],son[N],bel[N],dfn[N],idfn[N],idx=0;
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].v;
		if(to==fa[x]) continue;
		fa[to]=x;
		dep[to]=dep[x]+1;
		dis[to]=dis[x]+e[i].w; //前缀和 
		dfs1(to);
		sz[x]+=sz[to];
		if(sz[son[x]]<sz[to]) son[x]=to;
	}
}

void dfs2(int x,int tp){
	dfn[x]=++idx;
	idfn[idx]=x;
	bel[x]=tp;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].v;
		if(to==fa[x]||to==son[x]) continue;
		dfs2(to,to); 
	} 
}

#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)

int tr[N<<2],mi[N<<2],mx[N<<2];

void build(int p,int l,int r){
	if(l==r){
		tr[p]=mx[p]=mi[p]=dis[idfn[l]];
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[p]=tr[ls]+tr[rs];
	mi[p]=min(mi[ls],mi[rs]);
	mx[p]=max(mx[ls],mx[rs]);
}

int query(int p,int l,int r,int ql,int qr,int lim,int rt){
	if(ql<=l&&r<=qr&&mi[p]>=lim) return tr[p]-(r-l+1)*dis[rt];
	if(l==r) return 0;
	int res=0;
	if(ql<=mid&&mx[ls]>=lim) res=query(ls,l,mid,ql,qr,lim,rt);
	if(qr>mid&&mx[rs]>=lim) res+=query(rs,mid+1,r,ql,qr,lim,rt);
	return res; 
}

signed main(){
	int n,v,w,x,k,q;
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>v>>w;
		addedge(i,v,w);
	}
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>x>>k;
		if(sz[x]>0) cout<<query(1,1,n,dfn[x]+1,dfn[x]+sz[x]-1,dis[x]+k,x)<<"\n";
		else cout<<"0\n";
	}
	return 0;
}