https://codeforces.com/contest/1101/problem/D
题意
一颗n个点的树,找出一条gcd>1的最长链,输出长度
题解
- 容易想到从自底向长转移
- 因为只需要gcd>1即可,所以定义\(dp[u][i]\)为u的子树中和u相连的gcd含有i的最长链长度,i为素因子
- 这样对于每个点u,维护\(dp[u][i]\),用两条最长子链和u构成的链更新答案即可
代码
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
map<int,int>dp[MAXN];
int n,a[MAXN],u,v,ans,vi[MAXN];
vector<int>fac[MAXN],G[MAXN];
void init(){
for(int i=2;i<MAXN;i++)
if(!vi[i])
for(int j=i;j<MAXN;j+=i)
vi[j]=1,fac[j].push_back(i);
}
void dfs(int u,int fa){
map<int,int>mx,mx2;
for(auto v:G[u]){
if(v==fa)continue;
dfs(v,u);
int g=__gcd(a[u],a[v]);
for(auto x:fac[g]){
dp[u][x]=max(dp[v][x],dp[u][x]);
if(dp[v][x]>mx[x])mx2[x]=mx[x],mx[x]=dp[v][x];
else if(dp[v][x]>mx2[x])mx2[x]=dp[v][x];
ans=max(ans,mx[x]+mx2[x]+1);
}
}
for(auto x:fac[a[u]]){
dp[u][x]++;
ans=max(dp[u][x],ans);
}
}
int main(){
init();
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
cout<<ans;
}