求助Dsu On Tree

rt，94pts，wa on 5

Dsu On Tree+树状数组 做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &x){
    x=0;bool f=false;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}
template <typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
    return ;
}
const int N=5e6+5;
int n,m;
int head[N],nex[N],to[N],idx;
void add(int u,int v){
    nex[++idx]=head[u];
    to[idx]=v;
    head[u]=idx;
    return ;
}
#define int long long
struct query{int p,k,ans;}Q[N];
int Son[N],siz[N],fa[N],dep[N],sta[N],top,c[N];
bool vis[N];
vector<int> vec[N];
void Modify(int x,int v){
    for(;x<=n+10;x+=(x&(-x))) c[x]+=v;
    return ;
}
int Query(int x){
    int res=0;
    for(;x;x-=(x&(-x))) res+=c[x];
    return res;
}
void Dfs1(int x,int f){
    siz[x]=1,fa[x]=f;dep[x]=dep[f]+1;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f) continue;
        Dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>siz[Son[x]]) Son[x]=y;
    }
    return ;
}
int t[N],Mson,id,maxn;
void DFS(int x,int f,int tag){
    Modify(dep[x],(siz[x]-1)*tag);
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f||y==Mson) continue;
        DFS(y,x,tag);
    }
    return ;
}
void Dsu_On_Tree(int x,int f,int tag){
    Mson=id=maxn=0;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f||y==Son[x]) continue;
        Dsu_On_Tree(y,x,0);
    }
    if(Son[x]) Dsu_On_Tree(Son[x],x,1);
    Mson=Son[x];
    DFS(x,fa[x],1);
    for(int i=0;i<vec[x].size();i++){
        int k=vec[x][i],v=Q[k].k;
        Q[k].ans=Query(dep[x]+v)-Query(dep[x])+min(dep[x]-1,v)*(siz[x]-1);
    }
    if(!tag) Mson=maxn=id=0,DFS(x,fa[x],-1);
    return ;
}
int q;
signed main(){
    read(n),read(q);
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        add(u,v);
        add(v,u);
    }
    Dfs1(1,0);
    int ls=0;
    Dsu_On_Tree(1,0,0);
    for(int i=1;i<=q;i++){
        read(Q[i].p),read(Q[i].k);
        vec[Q[i].p].push_back(i);
    }
    Dsu_On_Tree(1,0,0);
    for(int i=1;i<=q;i++) write(Q[i].ans),putchar('\n');
    return 0;
}