死活94啊qwq

开O2 TLE 不开MLE

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

typedef long long ll;

struct node{
    int lch,rch;
    ll val;
}t[10000005];

int n,q,tot=0,cnt=0;
int dfn[300005],v[600005],next[600005],h[300005],dep[300005],vs[300005],rnk[300005];
ll size[300005];

void addedge(int x,int y){
    v[++tot]=y; next[tot]=h[x]; h[x]=tot;
    v[++tot]=x; next[tot]=h[y]; h[y]=tot;
}

void buildtree(int id,int l,int r){
    if(l==r)
        return;
    int mid=(l+r)/2;
    buildtree(t[id].lch=++tot,l,mid);
    buildtree(t[id].rch=++tot,mid+1,r);
}

int change(int id,int l,int r,int p,ll c){
    int root=++tot;
    t[root]=t[id];
    t[root].val+=c;
    if(l==r)
        return root;
    int mid=(l+r)/2;
    if(p<=mid)
        t[root].lch=change(t[root].lch,l,mid,p,c);
    else
        t[root].rch=change(t[root].rch,mid+1,r,p,c);
    return root;
}

ll query(int id1,int id2,int l,int r,int ql,int qr){
    if(l==ql&&r==qr)
        return t[id2].val-t[id1].val;
    int mid=(l+r)/2;
    if(qr<=mid)
        return query(t[id1].lch,t[id2].lch,l,mid,ql,qr);
    else if(ql>mid)
        return query(t[id1].rch,t[id2].rch,mid+1,r,ql,qr);
    else
        return query(t[id1].lch,t[id2].lch,l,mid,ql,mid)+query(t[id1].rch,t[id2].rch,mid+1,r,mid+1,qr);
}

void dfs(int u,int fa){
    size[u]=1,dfn[u]=++cnt,rnk[cnt]=u;
    for(int p=h[u];p;p=next[p]){
        if(v[p]==fa)
            continue;
        dep[v[p]]=dep[u]+1;
        dfs(v[p],u);
        size[u]+=size[v[p]];
    }
}

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

int main(){
    n=readint(); q=readint();
    int x,y;
    for(int i=1;i<=n-1;i++)
        addedge(readint(),readint());
    buildtree(vs[0]=0,1,n);
    dep[1]=1;
    dfs(1,-1);
    for(int i=1;i<=n;i++)
        vs[i]=change(vs[i-1],1,n,dep[rnk[i]],size[rnk[i]]-1);
    for(int i=1;i<=q;i++){
        x=readint(); y=readint();
        printf("%lld\n",min(dep[x]-1,y)*(size[x]-1)+query(vs[dfn[x]-1],vs[dfn[x]+size[x]-1],1,n,dep[x]+1,min(dep[x]+y,n)));
    }
    return 0;
}