反正肯定要建虚树，考虑建完之后怎么做

先随便dp一下算出来距离某点最近的询问点mi[x]（因为有的虚树上的点它不是询问点嘛）

那我们对于某条链x到fa[x]上的非虚树上的点（包括他们的非虚树上的孩子），要么把它分给mi[x]，要么分给mi[fa[x]]

我找到这个中间点以后，在原树上倍增跳过去，算他的size

这个分法是以$\frac{len[mi[x]]+len[x]+len[mi[fa[x]]]}{2}$再加加减减一些细节决定的（len[x]表示x到fa[x]的链的长度）

除此之外，每个在虚树上的点x（以及它不在虚树上的孩子），都归属于mi[x]

1 #include
     
        2 #define mp make_pair  3 #define CLR(a,x) memset(a,x,sizeof(a))  4 using namespace std;  5 typedef long long ll;  6 typedef unsigned long long ull;  7 typedef pair
      
        pa;  8 const int maxn=3e5+10,inf=1e9;  9  10 inline ll rd(){ 11     ll x=0;char c=getchar();int neg=1; 12     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();} 13     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 14     return x*neg; 15 } 16  17 int N,Q; 18 int eg[maxn*2][2],egh[maxn],ect; 19 int fa[maxn][22],dep[maxn],dfn[maxn],tot,siz[maxn]; 20  21 inline void adeg(int a,int b){ 22     eg[++ect][0]=b,eg[ect][1]=egh[a],egh[a]=ect; 23 } 24  25 inline void dfs1(int x){ 26     dfn[x]=++tot; 27     for(int i=0;fa[x][i]&&fa[fa[x][i]][i];i++){ 28         fa[x][i+1]=fa[fa[x][i]][i]; 29     } 30     siz[x]=1; 31     for(int i=egh[x];i;i=eg[i][1]){ 32         int b=eg[i][0];if(b==fa[x][0]) continue; 33         fa[b][0]=x,dep[b]=dep[x]+1; 34         dfs1(b);siz[x]+=siz[b]; 35     } 36 } 37  38 inline int jump(int x,int d){ 39     int i=0; 40     while(d){ 41         if(d&1) x=fa[x][i]; 42         i++,d>>=1; 43     }return x; 44 } 45  46 inline int getlca(int x,int y){ 47     if(dep[x]
       
        =0&&dep[x]!=dep[y];i--){ 49         if(dep[fa[x][i]]>=dep[y]) 50             x=fa[x][i]; 51     } 52     if(x==y) return x; 53     for(int i=log2(dep[x]);i>=0;i--){ 54         if(fa[x][i]!=fa[y][i])  55             x=fa[x][i],y=fa[y][i]; 56     } 57     return fa[x][0]; 58 } 59  60 inline bool cmp(int x,int y){
   return dfn[x]
        
         dfn[lca]){ 79             if(lst) connect(lst,stk[hd]); 80             lst=stk[hd--]; 81         }if(stk[hd]!=lca) stk[++hd]=lca,id[++pct]=lca; 82         if(lst) connect(lst,stk[hd]); 83         if(h[i]!=1) stk[++hd]=h[i]; 84     } 85     while(hd>1) connect(stk[hd],stk[hd-1]),hd--; 86 } 87 pa up[maxn],dw[maxn]; 88 inline void dfs2(int x){ 89     if(rea[x]) dw[x]=mp(0,x); 90     else dw[x]=mp(inf,0); 91     for(int i=xsh[x];i;i=xbr[i]){ 92         dfs2(i); 93         dw[x]=min(dw[x],mp(dw[i].first+len[i],dw[i].second)); 94     } 95 } 96 inline void dfs3(int x){ 97     if(rea[x]) up[x]=mp(0,x); 98     else if(x==1) up[x]=mp(inf,0); 99     pa m=mp(inf,0),s=mp(inf,0);100     for(int i=xsh[x];i;i=xbr[i]){101         s=min(s,mp(dw[i].first+len[i],dw[i].second));102         if(s
         
          >=1,n-=min(dw[x],up[x]).first;115         if(n>len[x]) n--;116         if(n>=0){117             int y=jump(x,n),z=jump(x,len[x]-1);118             ans[min(dw[x],up[x]).second]+=siz[y]-siz[x],ans[mi]+=siz[z]-siz[y];119         }120         121     }122     int ss=siz[x];123     for(int i=xsh[x];i;i=xbr[i]) ss-=siz[jump(i,len[i]-1)];124     ans[min(dw[x],up[x]).second]+=ss;125 }126 127 128 int hh[maxn];129 int main(){130     //freopen("","r",stdin);131     int i,j,k;132     N=rd();133     for(i=1;i