警示后人

千万不要图方便不把询问挂在点上搞什么点分树！！！

常数巨大！空间巨大！

喜提 TLE+MLE+40pts

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;

const int maxn=100010;

const char ze='0';

inline int fr(){
    int res=0;char tp=getchar();
    while(!isdigit(tp))tp=getchar();
    while(isdigit(tp)){
        res=(res<<3)+(res<<1)+tp-ze;
        tp=getchar();
    }
    return res;
}

int T;

int n,m;
//vector<int>go[maxn];

int head[maxn],nxt[maxn<<1],to[maxn<<1];
int tot=0;

inline void addedge(int x,int y){
    tot++;
    nxt[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

unordered_map<int,int>distp[maxn],distr[maxn];
int fa[maxn];int vis[maxn];

vector<int>poi[maxn],rc[maxn];

void getdist(int tar,int x,int f,int len,int mode){
    if(mode==1){
        distr[tar][x]=len;
        while(rc[tar].size()<len+1)rc[tar].pb(0);
        rc[tar][len]++;
    }
    else{
        distp[tar][x]=len;
        while(poi[tar].size()<len+1)poi[tar].pb(0);
        poi[tar][len]++;
    }
    int y;
    for(int i=head[x];i;i=nxt[i]){
        y=to[i];
        if(y==f||vis[y])continue;
        getdist(tar,y,x,len+1,mode);
    }
}

int getroot(int x,int f,int subsiz,int &submax,int &rt){
    int inmax=0,siz=1;
    int y;
    for(int i=head[x];i;i=nxt[i]){
        y=to[i];
        if(y==f||vis[y])continue;
        int res=getroot(y,x,subsiz,submax,rt);
        inmax=max(res,inmax);
        siz+=res;
    }
    inmax=max(inmax,subsiz-inmax);
    if(inmax<submax){
        submax=inmax;
        rt=x;
    }
    return siz;
}

int getsiz(int x,int f){
    int siz=1;
    int y;
    for(int i=head[x];i;i=nxt[i]){
        y=to[i];
        if(y==f||vis[y])continue;
        siz+=getsiz(y,x);
    }
    return siz;
}

void pre(int x,int subsiz,int f){
    int root,submax=0x3f3f3f3f;
    int trash=getroot(x,0,subsiz,submax,root);
    if(f)getdist(root,x,0,1,1);
    getdist(root,root,0,0,2);
    fa[root]=f;
    vis[root]=1;
    int y;
    for(int i=head[root];i;i=nxt[i]){
        y=to[i];
        if(vis[y]||y==f)continue;
        pre(y,getsiz(y,root),root);
    }
}

int query(int x,int dis,int tar){
    int res=0;
    if(dis-distp[x][tar]>=0&&dis-distp[x][tar]<poi[x].size())
    res+=poi[x][dis-distp[x][tar]];
    if(fa[x]){
        if(dis-distp[fa[x]][tar]>=0&&dis-distp[fa[x]][tar]<rc[x].size())
        res-=rc[x][dis-distp[fa[x]][tar]];
        res+=query(fa[x],dis,tar);
    }
    return res;
}

void solve(){
    n=fr();m=fr();
    memset(head,0,sizeof(head));tot=0;
    memset(vis,0,sizeof(vis));
    memset(fa,0,sizeof(fa));
    for(int i=1;i<=n;i++){
        poi[i].clear();rc[i].clear();distp[i].clear();distr[i].clear();
        //fa[i]=0;
    }
    int u,v;
    for(int i=1;i<n;i++){
        u=fr();v=fr();
        //go[u].pb(v);go[v].pb(u);
        addedge(u,v);
        addedge(v,u);
    }
    pre(1,n,0);
    int x,k;
    for(int i=1;i<=m;i++){
        x=fr();k=fr();
        printf("%d\n",query(x,k,x));
    }
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);

    T=fr();

    while(T--)solve();

    return 0;
}