WA 12

link

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300002
using namespace std;
namespace Graph{
    long long to[N*2],nxt[N*2],fir[N*2];
    long long tot=0;
    void add(long long x,long long y){
        to[++tot]=y;
        nxt[tot]=fir[x];
        fir[x]=tot;
    }
}
#define graph(u) for(long long i=Graph::fir[u];i;i=Graph::nxt[i])
namespace segment{
    long long size=0;
    struct node{
        long long ls,rs;
        long long d;
        node(){
            ls=rs=d=0;
        }
    }tree[6000000];
    #define ls(u) tree[u].ls
    #define rs(u) tree[u].rs
    #define d(u) tree[u].d
    void pushup(long long u){
        d(u)=d(ls(u))+d(rs(u));
        return ;
    }
    long long insert(long long u,long long l,long long r,long long pos,long long delta){
        if(!u) u=++size;
        if(l==r){
            d(u)+=delta; return u;
        }
        long long mid=(l+r)>>1;
        if(pos<=mid) ls(u)=insert(ls(u),l,mid,pos,delta);
        else rs(u)=insert(rs(u),mid+1,r,pos,delta);
        pushup(u);
        return u;
    }
    long long merge(long long p,long long q,long long l,long long r){
        if(!p) return q;
        if(!q) return p;
        if(l==r){
            d(p)+=d(q);
            return p;
        }
        long long mid=(l+r)>>1;
        ls(p)=merge(ls(p),ls(q),l,mid);
        rs(p)=merge(rs(p),rs(q),mid+1,r);
        pushup(p);
        return p;
    }
    inline long long query(long long u,long long x,long long y,long long l,long long r){
        if(!u) return 0;
        if(x==l&&r==y) return d(u);
        long long mid=(l+r)>>1;
        if(x<=mid) {
            if(y>mid) return query(ls(u),x,mid,l,mid)+query(rs(u),mid+1,y,mid+1,r);
            else return query(ls(u),x,y,l,mid);
        }
        return query(rs(u),x,y,mid+1,r);
    }
}
namespace IO {
    inline long long read(){
        char ch=getchar();
        long long x=0,f=1;
        while(ch<'0'||ch>'9'){
            if(ch=='-') f=-1;
            ch=getchar();
        }
        while('0'<=ch&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar();
        }
        return x*f;
    }
}
long long rt[N],n,m,M;
long long dep[N],size[N];
#define upd segment::insert
void dfs(long long u,long long f){
    dep[u]=dep[f]+1,size[u]=1;
    graph(u){
        long long v=Graph::to[i];
        if(v==f) continue;
        dfs(v,u),size[u]+=size[v];
        rt[u]=segment::merge(rt[u],rt[v],1,n);
    }
    rt[u]=upd(rt[u],1,n,dep[u],size[u]-1);
    return ;
}
int main(){
    n=IO::read(); m=IO::read();
    for(long long i=1;i<n;i++){
        long long x=IO::read(),y=IO::read();
        Graph::add(x,y),Graph::add(y,x);
    }
    dfs(1,0);
    while(m--){
        long long x=IO::read(),k=IO::read();
        long long ans=min(k,dep[x]-1)*(size[x]-1);
        ans+=segment::query(rt[x],dep[x]+1,min(n,dep[x]+k),1,n);
        printf("%lld\n",ans);
    }
    return 0;
}