题解 P7854 【「EZEC-9」GCD Tree】

· · 题解

首先点权相同的点显然可以缩在一起，这样剩下的点点权都是互不相同的。

因为当 a_i\mid a_j 时 \gcd(a_i,a_j)=a_i，显然此时 i 应该是 j 的祖先。所以我们考虑按点权从大到小枚举 i，对于所有点权为其倍数的还未设置父亲的点 j，将 j 的父亲设置为 i，全部设置完后再次枚举倍数检查是否成祖先关系（在这步之前要先检查是否连通）。

考虑如何处理类似 1 4 6 这种 \gcd 未出现的情况。

我们可以枚举 \gcd 的值，然后将点权为其倍数的点全部标记出来。可以发现如果所有被标记出来的点如果正好构成原树的一棵子树，那么这个 \gcd 的值是不会出现的；如果为多棵，那么就必然会有点对使得点权的 \gcd 的值为枚举到的值，也就是无解。

然后可以发现这步的判断可以和上面的判断合成一种判断。

复杂度 O(n\log n)（调和级数的复杂度）。

#include<bits/stdc++.h>
#define N 1000000
using namespace std;
int lw[100005],bi[100005][2],bs;
int n,a[100005],fa[100005],tt,rt;
int si[100005],hx[100005],dfn;
int xh[1000005];
int dr()
{
    int xx=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')xx=xx*10+ch-'0',ch=getchar();
    return xx;
}
void tj(int u,int v){bi[++bs][0]=lw[u],bi[lw[u]=bs][1]=v;}
void dfs(int w)
{
    si[w]=1,hx[w]=++dfn;
    for(int o_o=lw[w];o_o;o_o=bi[o_o][0])
    {
        int v=bi[o_o][1];
        dfs(v),si[w]+=si[v];
    }
}
bool gra(const int &x,const int &y){return hx[x]<=hx[y]&&hx[y]<hx[x]+si[x];}
int main()
{
    n=dr();
    for(int i=1;i<=n;i++)
    {
        a[i]=dr();
        if(xh[a[i]])fa[xh[a[i]]]=i,tj(i,xh[a[i]]),++tt;
        xh[a[i]]=i;
    }
    for(int i=N;i;i--)if(xh[i])
    {
        rt=xh[i];
        for(int j=i*2;j<=N;j+=i)if(xh[j]&&(!fa[xh[j]]))fa[xh[j]]=xh[i],tj(xh[i],xh[j]),++tt;
    }
    if(tt!=n-1){printf("-1");return 0;}
    dfs(rt);
    for(int i=1;i<=N;i++)
    {
        int tt=0;
        for(int j=i;j<=N;j+=i)if(xh[j]&&(fa[xh[j]]==0||a[fa[xh[j]]]%i!=0))++tt;
        if(tt>1){printf("-1");return 0;}
    }
    for(int i=1;i<=n;i++)printf("%d ",fa[i]);
}