友好国度-526互联

A开始与其他国家交流。

国家之间的交通关系可以抽象为一棵由 n 个节点组成的树，那么显然一个国家到另一个国家只存在唯一的简单道路。与此同时，每个国家还有一个友好度 ai，两个国家能够成为友好国度，当且仅当这两个国家的简单路径上所有点的友好度的最大公因数为 1。

A当然知道他与多少个国家是友好国度，不过现在A想问你，所有的国家一共有多少对是友好国度？

看似点分治，实则并查集。不过淀粉质可以做（

先把点权转化成边权，也就是把边权弄成起点和终点的gcd，然后计算值为i的倍数的路径数，用并查集维护，再然后计算值为i的路径数，最后输出值为1的倍数。每次枚举权值为i的倍数的边，然后在并查集里把边的起点和终点连起来，新增的值为i的倍数的路径数也就是起点所在的连通块的大小乘上终点所在的连通块的大小。

最后从大到小枚举，类似数学归纳法。刚刚枚举到i时，小于等于i的这一块还是值为i的倍数的路径数，大于i的这一块就是值为i的倍数的路径数。那么在处理i时，就可以把原来求出的值为i的倍数的路径数减去值为2i的路径数再减去值为3i的路径数等。最后剩下来的就是值为i的路径数。

时间复杂度 O(NlogN)（没算并查集的复杂度，而通过容斥推得不算并查集时间复杂度O(128N)是错的，这个log是调和级数来的）

#include<bits/stdc++.h>
#define fi    first
#define se    second
#define rev(x)    f[x]=x,siz[x]=1
using namespace std;
typedef long long ll;
const int N=1e5;
vector<pair<int,int> > t,tmp[N+9];
int n,a[N+9],f[N+9],siz[N+9];
ll res,ans[N+9];
int kf(int x)
{
    return f[x]==x?x:(f[x]=kf(f[x]));
}
void merge(int x,int y)
{
    x=kf(x);
    y=kf(y);
    res+=siz[x]*siz[y];
    f[x]=y;
    siz[y]+=siz[x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++)
    {
        cin>>x>>y;
        t.push_back({x,y});
    }
    for(int i=1;i<=n;i++)    cin>>a[i];
    for(auto v:t)    tmp[__gcd(a[v.fi],a[v.se])].push_back(v);
    for(int i=1;i<=n;i++)    rev(i);
    for(int i=1;i<=N;i++)
    {
        res=0;
        for(int j=i;j<=N;j+=i)
            for(auto v:tmp[j])    merge(v.fi,v.se);
        ans[i]=res;
        for(int j=i;j<=N;j+=i)
            for(auto v:tmp[j])
            {
                rev(v.fi);
                rev(v.se);
            }
    }
    for(int i=N>>1;i;i--)
        for(int j=i<<1;j<=N;j+=i)    ans[i]-=ans[j];
    cout<<ans[1];
    return 0;
}