1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include <bits/stdc++.h> #define REG register #define LL long long #define MAXN 300005 using namespace std; inline int read(){ REG int x(0); REG char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x*10)+(c^48),c=getchar(); return x; } inline int Min(int a,int b){return a<b?a:b;} inline int Max(int a,int b){return a>b?a:b;}
int n,q;
struct Edge{ int v,nxt; }ed[MAXN<<1]; int head[MAXN],cnt; inline void adde(int u,int v){ ed[++cnt]=(Edge){v,head[u]}; head[u]=cnt; } inline void add(int u,int v){adde(u,v),adde(v,u);}
#define Ls(now) (t[now].ls) #define Rs(now) (t[now].rs) #define mid ((l+r)>>1) int tot,rt[MAXN]; struct Tree{ LL val;int ls,rs; }t[MAXN<<8]; inline void Push_up(int now){t[now].val=t[Ls(now)].val+t[Rs(now)].val;} void Update(int& now,int l,int r,int pos,LL state){ if(!now) now=++tot; if(l==r) t[now].val+=state; else{ if(mid>=pos) Update(Ls(now),l,mid,pos,state); else Update(Rs(now),mid+1,r,pos,state); Push_up(now); } } LL Ask(int now,int l,int r,int x,int y){ if(!now||r<l) return 0; if(l>=x&&r<=y) return t[now].val; LL res(0); if(mid>=x) res+=Ask(Ls(now),l,mid,x,y); if(mid<y) res+=Ask(Rs(now),mid+1,r,x,y); return res; } int Merge(int a,int b){ if(!a||!b) return a|b; int now=++tot; t[now].val=t[a].val+t[b].val; Ls(now)=Merge(Ls(a),Ls(b)); Rs(now)=Merge(Rs(a),Rs(b)); return now; }
int siz[MAXN],dep[MAXN]; void dfs(int now,int fa){ siz[now]=1,dep[now]=dep[fa]+1; for(REG int i=head[now];i;i=ed[i].nxt){ int v=ed[i].v; if(v==fa) continue; dfs(v,now); siz[now]+=siz[v]; rt[now]=Merge(rt[now],rt[v]); } Update(rt[now],1,n,dep[now],siz[now]-1); }
int main(){ n=read(),q=read(); for(REG int i=1;i<n;++i) add(read(),read()); dfs(1,0); for(REG int i=1;i<=q;++i){ int p=read(),k=read(); printf("%lld\n",Ask(rt[p],1,n,dep[p]+1,dep[p]+k)+(LL)Min(k,dep[p]-1)*(siz[p]-1)); } }
|