什么是淀粉质点分治？

就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。

举个例子：

如何求出一颗树上距离为K且所经过的点最少的点对？

 

对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。

---

为什么要学淀粉质

对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能得到$O(n^2)$的暴力枚举，但是如果我们用淀粉质来搞，我们就可以做到$O(n*log_n)$的复杂度（如果K很大的话，我们可能还得套个数据结构上去，复杂度就变成了$O(n*log_n^2)$），我们就可以通过这类题目。

---

怎么淀粉质啊

正如我们刚刚说说的，淀粉质的实质是选出一个点，对其左右子树分治，再计算组合不同子树的答案。

所以说，我们在处理某颗子树之前，必须先选出来一个点作为这个子树的根。

我们选的这个点，对我们复杂度的影响极其巨大。

我们可以考虑选重心，重心就是指如果这个点做为根，其任意一颗子树大小均不会超过总点树的$1/2$。

如果我们每次对子树分治的时候，新选的根是重心，那我们的树的总层数一定不会超过$log_n$层。

对于找重心，我们每次都做一遍dfs就好。

int GetSize(int now){    t_vis[now]=true;    size[now]=1;    for(int i=0;i
     
      cnt/2) OK=false;            t_size+=size[e[now][i].to];        }    if(cnt-t_size>cnt/2) OK=false;    if(OK==true) root=now;    t_vis[now]=false;}
     

 

 

选出来重心之后，我们就可以以重心为根分治了。

首先，我们显然可以递归处理子树，然后再处理跨越两个子树的情况。

对于我们上面讲的那道题，我们所需要求的就是跨过两个子树且距离为K的点对的数量。

我们可以考虑这样做：

我们先开一个桶来记录长度为x的路径的点的数量，然后对每颗子树先做两遍dfs，第一遍先去桶里找到目前的点为止，之前找到的子树中有没有K-dis_now的路径。第二遍我们再把到每个点的距离放到桶里面去。

搞完之后，我们可以再dfs一次来回溯掉之前加上的东西，如果我们直接memset的话，会T的。

*注意：我们这里的dfs必须只能走已经分治完成的点，分治完成的点才是其儿子

void dfs2(int now,int dis,int t_cnt,int type){    t_vis[now]=true;    if(type==1 and K-dis>=0)        ans=min(ans,t_cnt+tot[K-dis]);    if(type==2 and dis
     
       son;    son.reserve(32);    for(int i=0;i
     

 

这样子搞，看起来时间复杂度很爆炸，其实并不大，因为我们最多有$log_n$层，每层做$n$次，总复杂度也就只有$O(n*log_n)$

这样子，我们就搞定啦φ(>ω<*) 

---

完整的代码

题目传送门：https://www.luogu.org/problemnew/show/P4149（题目稍有变动，但方法类似）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;long long read(){    long long x=0,f=1; char c=getchar();    while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();}    while(isdigit(c)){x=x*10+c-'0';c=getchar();}    return x*f;}const int N=200000+100;const int M=1000000+100;const int inf=0x3f3f3f3f;struct road{    int to,w;    road (int A,int B)    {        to=A,w=B;    }};vector 
         
           e[N];int n,K;bool vis[N],t_vis[N],done[N];int size[N],cnt,root;int GetSize(int now){    t_vis[now]=true;    size[now]=1;    for(int i=0;i
          
           (cnt/2)) OK=false; } if(cnt-t_size>(cnt/2)) OK=false; if(OK==true) root=now; t_vis[now]=false;}int ans=inf,tot[M];void dfs2(int now,int dis,int t_cnt,int type){ t_vis[now]=true; if(type==1 and K-dis>=0) ans=min(ans,t_cnt+tot[K-dis]); if(type==2 and dis
           
             son; son.reserve(32); for(int i=0;i
            
             N) ans=-1; printf("%d",ans); return 0;}