whx's Blog

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
using namespace std;
const int N = 300010;
typedef long long LL;
struct edge{
	int to,pre;
}e[N * 2];
int l = 0, u[N];
inline void ins(int a,int b){
	e[++l] = (edge){b, u[a]}, u[a] = l;
}
int pre[N], dep[N], dfs_clock = 0, last[N], sz[N];
void dfs(int x,int f){
	pre[x] = ++dfs_clock, sz[x] = 1;
	reg(i,x) if (v != f){
		dep[v] = dep[x] + 1, dfs(v,x), sz[x] += sz[v];
	}
	last[x] = dfs_clock;
}
#define mp(a,b) make_pair(a,b)
pair<int,int> y[N];
struct query{
	int l,r,t,pos,szp,dep,k;//(l,r]
}q[N];
LL ans[N];
inline bool cmp(const query &a, const query &b){
	return a.t < b.t;
}
inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}

    return x*f;

}
int n;
struct BIT{
	LL s[N];
	inline void add(int x, int d){
		while (x <= n){
			s[x] += d;
			x += (-x) & x;
		}
	}
	inline LL sum(int x){
		LL ans = 0;
		while (x > 0){
			ans += s[x];
			x -= (-x) & x;
		}
		return ans;
	}
}b;
#undef v
int main(){
	int Q;n = read(); Q= read();
	rep(i,1,n-1){
	    int u,v;
	    u = read(),v = read();
		ins(u,v), ins(v,u);
	}
	dep[1] = 1;dfs(1,0);
	rep(i,1,n) y[i] = mp(dep[i],i);
	sort(y+1, y+n+1);
	rep(i,1,Q){
		int p, k;p = read(), k =read();
		q[i] = (query){pre[p], last[p], dep[p] + k, i, sz[p], dep[p], k};
	}
	sort(q+1, q+Q+1, cmp);

	int j = 1;
	rep(i,1,Q){
		for(;y[j].first <= q[i].t && j <= n; j++) {
			int x = y[j].second;
			b.add(pre[x], sz[x] - 1);
		}
		ans[q[i].pos] = b.sum(q[i].r) - b.sum(q[i].l) +1LL * min(q[i].k, q[i].dep - 1) * (q[i].szp - 1);
	}
	rep(i,1,Q) printf("%lld\n", ans[i]);
}