题目分析：

树上点对问题首先想到点分治。假设我们进行了点分治并递归地解决了子问题。现在我们合并问题。

我们需要找到所有经过当前重心$ c $的子树路径。第一种情况是LCA为当前重心$ c $。考虑以$ 1 $为根的$ c $的子树。那么首先在子问题中先斥掉不经过$ c $的路径。然后对于$ c $的子树处理出距离数组。用桶存储。

从大到小枚举最大公因数$ d $，求出所有距离为$ d $倍数的点的个数。然后做乘法得到$ num1 $。再考虑$ num1 $中GCD不等于$ d $的数有哪些。实际上我们早就计算出了GCD为$ d $的倍数的情况了，只需要把这一部分斥掉就行了。所以处理$ c $的子树的点对的时间复杂度是$ O(nlogn) $。

再考虑$ c $的祖先的儿子到$ c $的子树中的点的情况。不难想到类似的处理方法。开个桶存储距离。由于点分治的特性。我们很容易就可以证明这样所有桶的最大值之和是不会超过$ O(n) $的。这样枚举的时间复杂度是有保障的。对于$ c $的某个祖先的子树中的点，枚举GCD为$ d $。 那么我们要在$ c $的子树中找到所有的距$ c $祖先$ d $的倍数的点。 由于我们拔高了LCA，这时候我们不能简单地枚举倍数。重新审视问题，发现其实它是求的c中从i开始每隔j个的和。采用分块算法，对于小于等于$ \sqrt{n} $的情况共有$ \sqrt{n} $个不同的起点。每个不同的间隔都会完全覆盖依次整个桶。共覆盖了$ \sqrt{n} $次。所以预处理的时间复杂度为$ O(n*\sqrt{n}) $。对于大于$ \sqrt{n} $的情况可以暴力计算。 

我们每处理一个重心的时间复杂度为$ O(n*\log n+n*\sqrt{n}) $分为两半，前半部分总时间复杂度为$ O(n*\log n*\log n) $，后半部分带入主定理知为$ O(n*\sqrt{n}) $

 

代码：

 

1 #include
     
        2 using namespace std;  3   4 const int maxn = 200005;  5   6 int n;  7 int dep[maxn],f[maxn];  8 long long ans[maxn];  9 vector 
      
        g[maxn]; 10  11 int arr[maxn],sz[maxn],dg[maxn],presum[maxn]; 12  13 void read(){ 14     scanf("%d",&n); 15     for(int i=2;i<=n;i++) { 16     scanf("%d",&f[i]); 17     g[f[i]].push_back(i); 18     g[i].push_back(f[i]); 19     } 20 } 21  22 void DFS(int now,int dp) { 23     dep[now] = dp; 24     for(int i=0;i
       
         dg[z])res = z; 49     } 50     return res; 51 } 52  53 int depest,h[maxn],sum[maxn]; 54 long long nowans[maxn]; 55 int Final[500][500]; 56  57 int oth,arv[maxn],s2[maxn]; 58  59 void dfs3(int now,int len,int stop){ 60     h[len]++;depest = max(depest,len); 61     for(int i=0;i
        
         =1;i--){ 81     for(int j=1;i*j<=depest;j++) sum[i] += h[i*j]; 82     nowans[i] = 1ll*sum[i]*(sum[i]-1)/2; 83     for(int j=2;i*j<=depest;j++) nowans[i]-=nowans[i*j]; 84     ans[i] -= nowans[i]; 85     } 86     for(int i=0;i<=depest;i++) h[i] = 0,sum[i] = 0,nowans[i] = 0; 87 } 88  89 void solve_add(int now,int ht){ 90     depest = 0; 91     dfs3(now,0,ht); 92     for(int i=depest;i>=1;i--){ 93     for(int j=1;i*j<=depest;j++) sum[i] += h[i*j]; //multi d 94     nowans[i] = 1ll*sum[i]*(sum[i]-1)/2; 95     for(int j=2;i*j<=depest;j++) nowans[i]-=nowans[i*j]; 96     ans[i] += nowans[i]; 97     } 98     for(int i=1;i<=depest;i++) nowans[i] = 0; 99     100     for(int i=1;i*i<=depest;i++) for(int j=0;j
         
          ht||arr[tp] == 0)){106     oth = 0;rem++;107     dfs4(tp,last,ht,tp); // tp mean lca108     for(int i=oth;i>=1;i--){109         for(int j=1;i*j<=oth;j++) s2[i] += arv[i*j];110         if(i*i<=depest) 111         nowans[i] = 1ll*s2[i]*Final[i][(((-rem)%i)+i)%i];112         else{113         int frst = (((-rem)%i)+i)%i;114         int tot = 0;115         for(int k =frst;k<=depest;k+=i) tot += h[k];116         nowans[i] = 1ll*s2[i]*tot;117         }118         for(int j=2;i*j<=oth;j++) nowans[i] -= nowans[i*j];119         ans[i] += nowans[i];120     }121     last = tp; tp = f[tp];122     for(int i=0;i<=oth;i++) arv[i] = s2[i] = nowans[i] = 0;123     }124     //out subtree125     for(int i=0;i<=depest;i++) h[i] = 0,sum[i] = 0;126     for(int i=1;i*i<=depest;i++) for(int j=0;j
          
           =1;i--) presum[i] += presum[i+1];146 for(int i=1;i<=n;i++) ans[i] += presum[i];147 for(int i=1;i