D. GCD Counting 树形dp

题意：一棵树，每个节点有权值，找一条gcd不唯一的最长路，输出长度。

思路：gcd不唯1，即两个数有相同的素因子，dp[i][j]就表示以i个节点通过这个数的第j个素因子最长的子链，然后路的长度就是在遍历的时候选两个最长的相加，dfs遍历一遍树不断更新答案。

#include<bits/stdc++.h>
using namespace std;
int dp[200005][30];
bool isprime[200005];
int n,s,e,x,ans;
struct code
{
int to,nx;
} edge[500005];
int head[200005];
int daptop=0;
void add(int s,int e)
{
edge[daptop].to=e;
edge[daptop].nx=head[s];
head[s]=daptop++;
edge[daptop].to=s;
edge[daptop].nx=head[e];
head[e]=daptop++;
}
int prime[200005],top,nub[200005][32];
void check()
{
for(int i=2; i<200005; i++)
{
if(isprime[i]==0)
prime[top++]=i;
for(int j=0; j<top&&i*prime[j]<200005; j++)
{
prime[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
}
void dfs(int x,int from)
{
for(int i=head[x]; i!=-1; i=edge[i].nx)
{
int to=edge[i].to;
if(to==from)
continue;
dfs(to,x);
for(int k=1; k<=nub[x][0]; k++)
{
for(int tk=1; tk<=nub[to][0]; tk++)
{
if(nub[x][k]==nub[to][tk])
{
ans=max(ans,dp[x][k]+dp[to][tk]+1);
dp[x][k]=max(dp[x][k],dp[to][tk]+1);
}
}
}
}
}
int main()
{
check();
int flot=1;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
if(x!=1)
flot=0;
for(int j=0; j<top&&prime[j]*prime[j]<=x; j++)
{
if(x==1)
break;
if(x%prime[j]==0)
{
nub[i][++nub[i][0]]=prime[j];
while(x%prime[j]==0)
x/=prime[j];
}
}
if(x!=1)
nub[i][++nub[i][0]]=x;
}
for(int i=1; i<=n; i++)
head[i]=-1;
for(int i=0; i<n-1; i++)
{
scanf("%d%d",&s,&e);
add(s,e);
}
if(flot)
{
printf("0n");
return 0;
}
dfs(1,1);
printf("%dn",ans+1);
return 0;
}
//分解素因子一定用根号n的

最后

以上就是隐形猫咪最近收集整理的关于D. GCD Counting 树形dp的全部内容，更多相关D.内容请搜索靠谱客的其他文章。