Codeforces | 1101D GCD Counting | 动态规划 | 树规

---

Description

给出一棵树，树有点权，求树上长度最长的一条链，满足链上所有点的点权的 $\gcd > 1$。一个点也算一条链。

---

Input Format

第一行一个正整数 $n$ 表示树的点数。

接下来一行 $n$ 个正整数 $a_i$ 表示每个点的点权。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示树上的一条边。

---

Output Format

一行一个整数，如果不存在这样的链输出0，否则输出最长的可能链长。

---

Input Sample

Sample 01

3
2 3 4
1 2
2 3

Sample 02

3
2 3 4
1 3
2 3

Sample 03

3
1 1 1
1 2
2 3

---

Output Sample

Sample 01

1

Sample 02

2

Sample 03

0

---

Data Range

$1 \le n,a_i \le 2 \times 10^5$。

---

Solution

树归。考虑分解每个点的质因子。

设 $F[i][j]$ 表示结点 $i$ 的第 $j$ 个质因子向下能够延伸的最长长度。由于因子个数极少，枚举转移即可。

---

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::lower_bound;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct edge{
    int from;
    int to;
    int next;
}e[400005];

int N;
int po;
int ans;
int cnt;
int node;

int w[200005];
int primes[20005];
int first[200005];
int last[200005];
int f[200005][9];
int d[200005][9];

bool vis[200005];
bool isprime[200005];

void addedge(int u,int v){
    e[++node]=(edge){u,v,0};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void Euler_Sieve(int Lim){
    rep(i,2,Lim){
        if(!isprime[i])
            primes[++cnt]=i;
        for(int j=1;j<=cnt&&i*primes[j]<=Lim;j++){
            isprime[i*primes[j]]=1;
            if(i%primes[j]==0)
                break;
        } 
    }
    return;
}

void Decompose(){
    rep(i,1,N){
        int x=w[i];
        rep(j,1,cnt){
            if(x%primes[j]==0){
                ans=1;
                x/=primes[j];
                f[i][++f[i][0]]=primes[j];
                while(x%primes[j]==0)
                    x/=primes[j];
            }
            if(primes[j]*primes[j]>x)
                break;
        }
        if(x>1)
            f[i][++f[i][0]]=x,ans=1;
    }
    return;
}

void DFS(int x){
    vis[x]=1;
    rep(i,1,f[x][0])
        d[x][i]=1;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(vis[y])
            continue;
        DFS(y);
        rep(i,1,f[x][0]){
            po=lower_bound(f[y]+1,f[y]+1+f[y][0],f[x][i])-f[y];
            if(f[y][po]==f[x][i]){
                ans=max(ans,d[y][po]+d[x][i]);
                d[x][i]=max(d[x][i],d[y][po]+1);
            }
        }
    }
    return;
}

int main(){
    int fr;
    int to;
    int maxw=0;
    Read(N);
    rep(i,1,N){
        Read(w[i]);
        maxw=max(maxw,w[i]);
    }
    Euler_Sieve(maxw);
    Decompose();
    rep(i,2,N){
        Read(fr);
        Read(to);
        addedge(fr,to);
        addedge(to,fr);
    }
    DFS(1);
    printf("%d\n",ans);
    return 0;
}