Description

 

Input

Output

 

Sample Input

10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 5 2 6 1 5 2 7 3 6 9 1 8 4 8 7 10 3 5 2 9 3 5 8

Sample Output

1 9 3 1 4 1 1 10 1 1 3 5 4 1 3 1 1

 

Data Constraint

 

Hint

 

 

我们每次询问的关键点个数是有限的，实树上很多节点的情况实际是一样的，我们可以直接一起处理。

那么我们要构建一个叫虚树的东西。只把和这几个点有关系的点建入树中，没有在虚树中的点直接用size统计答案即可

虚树中要放入关键点以及dfs序相序关键点的lca。构建虚树的方法：用单调栈维护树的最右链，每加入一个点，把之前非父亲的点弹出，然后和父亲连边即可

 

然后我们在虚树上跑最短路，找出离每个点最近的点，

接着对于虚树的每一条边，

1.如果两端点的最近点相同，那么这条边上的最近点均相同，直接计入答案即可

2.不同，则在边上找一个分界点，然后用1的情况处理即可

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct dd{ int dis,x; bool operator < (dd a) const { return dis>a.dis; } dd(int a=0,int b=0){ dis=a; x=b; }};priority_queue
            
              H;int num[300011],a[300011],ys[300011],stk[300011],ans[300011];int t,T,tc,ts,tot,tt,top,n,m,i,j,x,z,root;int dfn[300011],next[600011],y[600011],g[300011],dep[300011];int G[300011],Next[600011],Y[600011],len[600011];int fa[300011][19],d[300011],near[300011],rank[300011],size[300011];bool vis[300011];bool cmp(int a,int b){ return dfn[a]
             
              =0;i--)if(fa[x][i]!=fa[z][i]){ x=fa[x][i]; z=fa[z][i]; } return fa[x][0];}void Buildtree(){ int i; sort(num+1,num+1+t,cmp); T=t; for(i=1;i
              
               =dfn[stk[top]]&&dfn[a[i]]
               
                0){ fj=ef(x,z,1,dep[x]-dep[z]-1); ans[rank[near[x]]]+=size[fj]-size[x]; ans[rank[near[z]]]+=size[nk]-size[fj]; } }}void find(int x,int faf){ int ad,j,k,nk; if(x==root)ans[rank[near[x]]]+=n-size[x]; j=G[x]; ad=size[x]; while(j!=0){ k=Y[j]; if(k!=faf){ nk=jump(k,dep[k]-dep[x]-1); Tfind(k,x); find(k,x); ad-=size[nk]; } j=Next[j]; } ans[rank[near[x]]]+=ad;}int main(){ scanf("%d",&n); for(i=1;i