【题意】给定n个点的树，m次询问，每次给定ki个特殊点，一个点会被最近的特殊点控制，询问每个特殊点控制多少点。n,m,Σki<=300000。

【算法】虚树+倍增

【题解】★参考：

对询问建立虚树，然后DFS统计虚树上每个点被哪个点控制，记为belong[x]。

统计的方法是从下往上DFS得到x来自x子树的控制点，再从上往下DFS得到x来自非x子树的控制点。

令D(x,y)表示点x和点y之间的路径长度，比较x的不同控制点y的方式是取D(x,y)的最小值（相同时比较编号）。

 

依此考虑虚树上的每一条边(x,y)，记z为同时是x的儿子和y的祖先的点，令f[x]表示点x的答案。

如果belong[x]=belong[y]，那么f[belong[x]]+=size[z]-size[y]

否则，从y倍增找到分界点mid，满足mid及以下由y控制，mid以上由x控制。

倍增过程中，记A=D(belong[x],mid),B=D(belong[x],mid)，当满足A>B或A=B&&belong[x]>belong[y]时进行倍增。

找到分界点mid后，f[belong[x]]+=size[x]-size[m]，f[belong[y]+=size[m]-size[y]。

 

最后要处理没有出现在虚树路径上的点（包括虚树节点），这些点没有在上述过程中被统计。

记rem[x]表示子树x中未被统计的节点数，初始rem[x]=size[x]，特别的rem[a[1]]=n（a[1]是虚树最高节点，n是原树总点数，这样是为了保存a[1]往上延伸的节点）

每次处理完边(x,y)，rem[x]-=size[z]。

全部做完后，对虚树的每个点f[belong[x]]+=rem[x]。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    int s=0,t=1;char c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=300010;int n,N,size[maxn],in[maxn],ou[maxn],f[maxn],a[maxn*2],b[maxn];int deep[maxn],tot,first[maxn],belong[maxn],st[maxn];int rem[maxn];bool v[maxn];namespace cyc{    int first[maxn],tot,dfsnum=0,f[maxn][30];    struct edge{
    int v,from;}e[maxn*2];    void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}    void dfs(int x,int fa){        in[x]=++dfsnum;size[x]=1;        for(int j=1;(1<
          
           <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];        for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){            deep[e[i].v]=deep[x]+1;            f[e[i].v][0]=x;            dfs(e[i].v,x);            size[x]+=size[e[i].v];        }        ou[x]=dfsnum;    }    int lca(int x,int y){        if(deep[x]
           
            =0;j--)if((1<
            
             <=deep[x]&&f[x][j]!=f[y][j]){ x=f[x][j];y=f[y][j]; } return f[x][0]; } void build(){ n=read(); for(int i=1;i
             
              =0;i--)if((1<
              
               <=deep[z]&&deep[cyc::f[z][i]]>=deep[x]+1)z=cyc::f[z][i]; rem[x]-=size[z]; if(belong[x]==belong[y]){f[belong[x]]+=size[z]-size[y];return;}// int m=y; for(int i=20;i>=0;i--)if((1<
               
                <=deep[m]){ if(deep[cyc::f[m][i]]
                
                 belong[y]))m=cyc::f[m][i];// } f[belong[x]]+=size[z]-size[m]; f[belong[y]]+=size[m]-size[y];}void work(){ int last=read();N=last; for(int i=1;i<=N;i++)a[i]=read(),f[b[i]=a[i]]=0,v[a[i]]=1; sort(a+1,a+N+1,cmp); for(int i=1;i
                
               
              
             
            
           
          
         
        
       
      

 （倍增求LCA）

 

 

 

注意，由于多次调用LCA，所以用倍增LCA算法有很大的常数，甚至在LOJ会导致TLE。

但是倍增求LCA会使过程更简洁。

下面这份代码是树链剖分求LCA，代码可读性不高。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    int s=0,t=1;char c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=300010;int n,N,size[maxn],in[maxn],ou[maxn],f[maxn],a[maxn*2],b[maxn];int deep[maxn],tot,first[maxn],belong[maxn],st[maxn];int rem[maxn];bool v[maxn];namespace cyc{    int first[maxn],tot,dfsnum=0,f[maxn][30];    struct edge{
    int v,from;}e[maxn*2];    void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}    void dfs(int x,int fa){        in[x]=++dfsnum;size[x]=1;        for(int j=1;(1<
          
           <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];        for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){            deep[e[i].v]=deep[x]+1;            f[e[i].v][0]=x;            dfs(e[i].v,x);            size[x]+=size[e[i].v];        }        ou[x]=dfsnum;    }    int lca(int x,int y){        if(deep[x]
           
            =0;j--)if((1<
            
             <=deep[x]&&f[x][j]!=f[y][j]){ x=f[x][j];y=f[y][j]; } return f[x][0]; } void build(){ n=read(); for(int i=1;i
             
              =0;i--)if((1<
              
               <=deep[z]&&deep[cyc::f[z][i]]>=deep[x]+1)z=cyc::f[z][i]; rem[x]-=size[z]; if(belong[x]==belong[y]){f[belong[x]]+=size[z]-size[y];return;}// int m=y; for(int i=20;i>=0;i--)if((1<
               
                <=deep[m]){ if(deep[cyc::f[m][i]]
                
                 belong[y]))m=cyc::f[m][i];// } f[belong[x]]+=size[z]-size[m]; f[belong[y]]+=size[m]-size[y];}void work(){ int last=read();N=last; for(int i=1;i<=N;i++)a[i]=read(),f[b[i]=a[i]]=0,v[a[i]]=1; sort(a+1,a+N+1,cmp); for(int i=1;i
                
               
              
             
            
           
          
         
        
       
      

 

upd：复习一下。

【建虚树】

第一步、所有关键点按DFS序排序，加入LCA后排序去重。

第二步、按顺序用栈维护构造出虚树。

第三步、虚树DP后清零。

【此题的虚树DP】

第一步、处理虚树上点与点。

第二步、处理虚树边上点的子树。

第三步、处理虚树点的 [ 不在虚树上的孩子 ] 子树。（通过减虚树孩子的sz得到）