树上差分 95分 WA#6

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<vector>
using namespace std;
struct node{
	long long k,id;
};
const int maxn=6e6+10;
vector<node> v[maxn];
vector<int> g[maxn];
long long ans[maxn];
long long p[maxn],kk[maxn];
long long dep[maxn],sz[maxn];
long long c[maxn],x,y,n,q;
int lowbit(int x){
	return x&(-x);
}
void add(int now,int x){
	while(now<=n){
		c[now]+=x;
		now+=lowbit(now);
	}
}
long long query(int now){
	long long res=0;
	while(now>0){
		res+=c[now];
		now-=lowbit(now);
	}
	return res;
}
void dfs2(int now,int fa){
	for(auto x:v[now]){
		int k=x.k;
		ans[x.id]-=(query(dep[now]+k)-query(dep[now]));
	}
	add(dep[now],sz[now]-1);
	for(auto x:g[now]){
		if(x==fa){
			continue;
		}
		dfs2(x,now);
	}
	for(auto x:v[now]){
		int k=x.k;
		ans[x.id]+=(query(dep[now]+k)-query(dep[now]));
	}
}
void dfs1(int now,int fa){
	dep[now]=dep[fa]+1;
	sz[now]=1;
	for(auto x: g[now]){
		if(x!=fa){
			dfs1(x,now);
			sz[now]+=sz[x];
		}
	}
}
void read(){
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=q;i++){
		cin>>p[i]>>kk[i];
		v[p[i]].push_back({kk[i],i});
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=q;i++){
		//cout<<ans[i]<<'*'<<endl;
		ans[i]+=(dep[p[i]]-max(1ll,dep[p[i]]-kk[i]))*(sz[p[i]]-1);
		cout<<ans[i]<<endl;
	}
}
int main(){
	read();
	return 0; 
}