看到要求gcd不为1所以肯定在这条答案链上都是一个质数的倍数,所以就会产生一个很暴力的想法
没错,正解就是这样的暴力
只让走是i(素数)倍数的点,作最长链
最长链可以树形dp或两遍bfs,一遍找端点,一遍过长度即可
复杂度:未证
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } map<int,int> ma; struct node{ int u,v,nex; }x[200001]; int cnt,n,head[100001]; void add(int u,int v) { x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++; } int v[100001],sry,have[100001]; int vis[100001]; int dis[100001]; vector<int> ve[100005]; int vis1[100001]; int maxn; int bfs(int u) { queue<int> que; int ans=u; que.push(u); vis[u]=1,dis[u]=1; while(!que.empty()) { int xx=que.front();que.pop(); for(int i=head[xx];i!=-1;i=x[i].nex) { if(have[x[i].v]==0) continue; if(vis[x[i].v]) continue; vis[x[i].v]=1; dis[x[i].v]=dis[xx]+1; if(dis[x[i].v]>dis[ans]) ans=x[i].v; que.push(x[i].v); } } while(!que.empty()) que.pop(); que.push(ans),vis1[ans]=1,dis[ans]=1; while(!que.empty()) { int xx=que.front();que.pop(); for(int i=head[xx];i!=-1;i=x[i].nex) { if(have[x[i].v]==0) continue; if(vis1[x[i].v]) continue; dis[x[i].v]=dis[xx]+1; vis1[x[i].v]=1; if(dis[x[i].v]>dis[ans]) ans=x[i].v; que.push(x[i].v); } } return dis[ans]; } int main() { memset(head,-1,sizeof(head)); n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); add(u,v),add(v,u); } for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<=n;i++) { int x=v[i]; for(int j=2;j<=sqrt(x);j++) { if(x%j!=0) continue; if(ma[j]==0) ma[j]=++sry; ve[ma[j]].push_back(i); while(x%j==0) x/=j; } if(x!=1) { if(ma[x]==0) ma[x]=++sry; ve[ma[x]].push_back(i); } } for(int i=1;i<=sry;i++) { int size=ve[i].size(); for(int j=0;j<size;j++) have[ve[i][j]]=1,vis[ve[i][j]]=0,vis1[ve[i][j]]=0; for(int j=0;j<size;j++) { if(vis[ve[i][j]]==1) continue; maxn=max(maxn,bfs(ve[i][j])); } for(int j=0;j<size;j++) have[ve[i][j]]=0,vis[ve[i][j]]=1,vis1[ve[i][j]]=1; } cout<<maxn; }