树上莫比乌斯反演+分层图并查集——cf990G

/*

树上莫比乌斯反演

求树上 满足 d|gcd(au,av) gcd(au,av)的对数f(d)

如何求：

    建立200000层新图，即对于每个数建立一个新图

    在加边时，给gcd(au,av)的约数层的图的uv加边

    f[i]表示第i层的满足条件 i | gcd(a[u],a[v]) 的对数,那么求一遍并查集，在合并过程中更新f[i]即可，

        同时要注意f[i]初始值为这层的有效结点数量，对应i|gcd(a[u],a[u])这样的情况

然后用莫比乌斯反演来求最后答案g[d]=sigma(u[i]*f[i*d])

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 200005

int phi[maxn],mu[maxn],prime[maxn],m;

bool vis[maxn];

void init(){//打表mu

    phi[]=mu[]=;

    for(int i=;i<maxn;i++){

        if(!vis[i]){

            mu[i]=-;prime[++m]=i;phi[i]=i-;

        }

        for(int j=;j<=m;j++){

            if(i*prime[j]>=maxn)break;

            vis[i*prime[j]]=;

            if(i%prime[j]==){

                phi[i*prime[j]]=phi[i]*prime[j];

                mu[i*prime[j]]=;

                break;

            }

            else phi[i*prime[j]]=phi[i]*(prime[j]-),mu[i*prime[j]]=-mu[i];

        }

    }

}

int n,a[maxn];

long long f[maxn],u[maxn],v[maxn];

vector<int>vec[maxn];//每层的边的下标集合

int F[maxn],size[maxn];

int find(int x){

    return F[x]==x?x:F[x]=find(F[x]);

}

void bing(int i,int u,int v){

    int t1=find(u),t2=find(v);

    if(t1==t2)return;

    f[i]+=(long long)size[t1]*size[t2];

    size[t1]+=size[t2];F[t2]=t1;

}

int main(){

    init();

    cin>>n;

    for(int i=;i<=n;i++){

        cin>>a[i];

        for(int j=;j*j<=a[i];j++)

            if(a[i]%j==){

                f[j]++;

                if(a[i]/j!=j)f[a[i]/j]++;

            }

    }

    for(int i=;i<n;i++){//建立2000000层新图

        scanf("%d%d",&u[i],&v[i]);

        int tmp=__gcd(a[u[i]],a[v[i]]);

        for(int j=;j*j<=tmp;j++)

            if(tmp%j==){

                vec[j].push_back(i);

                if(tmp/j!=j)

                    vec[tmp/j].push_back(i);

            }

    }

    //求并查集

    for(int i=;i<=;i++){

        for(int j=;j<vec[i].size();j++){//先初始化每层对应的并查集

            int uu=u[vec[i][j]],vv=v[vec[i][j]];

            F[uu]=uu;F[vv]=vv;

            size[uu]=;size[vv]=;

        }

        for(int j=;j<vec[i].size();j++){//再进行合并求值

            int uu=u[vec[i][j]],vv=v[vec[i][j]];

            bing(i,uu,vv);

        }

    }

    //反演+输出

    for(int d=;d<=;d++){

        long long ans=;

        for(int i=;i*d<=;i++)

            ans+=(long long)mu[i]*f[i*d];

        if(ans!=)

            cout<<d<<" "<<ans<<'\n';

    }

}