#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]); }