求查错

思路还是比较清晰的

线段树合并

但是只有12分？？

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
inline int read(){
    int x=0; char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x;
}
const int N=5e5+5,M=1e7+1;
int nxt[N<<1],head[N],go[N<<1],tot;
inline void add(int u,int v){
    nxt[++tot]=head[u],head[u]=tot,go[tot]=v;
    nxt[++tot]=head[v],head[v]=tot,go[tot]=u;
}
vector<pair<int,int> >Q[N];
int val[M],sum[M],ls[M],rs[M],root[N],cnt;
#define mid ((l+r)>>1)
inline void pushup(int p){
    val[p]=val[ls[p]]+val[rs[p]];
    sum[p]=sum[ls[p]]+sum[rs[p]];
}
void update(int &p,int l,int r,int pos,int d){
    if(!p)p=++cnt;
    if(l==r){ val[p]+=d; sum[p]++; return; }
    if(pos<=mid)update(ls[p],l,mid,pos,d);
    else update(rs[p],mid+1,r,pos,d);
    pushup(p);
}
int Val,Sum;
void query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R){ Val+=val[p],Sum+=sum[p]; return; }
    if(L<=mid)query(ls[p],l,mid,L,R);
    if(R>mid)query(rs[p],mid+1,r,L,R);
}
int merge(int u,int v,int l,int r){
    if(!u||!v)return u|v;
    if(l==r){ val[u]+=val[v],sum[u]+=sum[v]; return u; }
    ls[u]=merge(ls[u],ls[v],l,mid);
    rs[u]=merge(rs[u],rs[v],mid+1,r);
    pushup(u);
    return u;
}
int dep[N],Ans[N],siz[N],n,q;
void dfs(int u,int fa){
    dep[u]=dep[fa]+1,siz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=go[i];
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
    for(int i=0;i<Q[u].size();i++){
        int k=Q[u][i].fi;
        int ans= min(dep[u]-1,k) * (siz[u]-1) ;
        Val=0,Sum=0;
        query(root[u],1,n,0,k+dep[u]); 
        ans+= Val- Sum*dep[u] -Sum ;
        Ans[Q[u][i].se]=ans;
    }
    update(root[u],1,n,dep[u],dep[u]);
    if(fa)root[fa]=merge(root[fa],root[u],1,n);
}

signed main(){
    n=read(),q=read();
    for(int i=1;i<n;i++)add(read(),read());
    for(int i=1,x,y;i<=q;i++){
        x=read(),y=read();
        Q[x].pb(mp(y,i));
    }
    dfs(1,0);
    for(int i=1;i<=q;i++)printf("%lld\n",Ans[i]);
}