传送门
题意：给一棵n个点的数以及n个点的点权，一条路径(x,y)合法当且仅当从x到y的路径上所有点权的gcd大于1（一条路径也可以是一个点），问所有合法路径经过的点的数量最大的经过了多少点。
题解：就是求最长的合法路径再+1。这种在树上询问路径的可以优先考虑点分治。每次分治到一个重心，把每条链的链上gcd分解质因数，去和之前这些质因数对应的最大链长加起来再+1，然后这些质因数对应的最大链长都更新一下。注意每次先把一棵子树中的链记下来，先询问再更新（避免同一棵子树内的两条链更新答案）。
还是要注意先加入重心本身这条链（一个点），老是忘这操作......
最终还要考虑一下一个点这种情况，因为有可能不存在两个不同的点使得路径上点权gcd大于1，那么如果这时某个点自身的点权大于1，答案就是1而非0（样例1和样例3对比一下）。
交上去居然1A，之前可是做好了调半个下午的思想准备的......但是这带了剪枝（一条链的gcd已经为1就不再往下求dis了）都还4000多ms也是跑得巨慢诶...
P.S.好像还可以用树形dp做？
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<utility> using namespace std; const int N=2e5+4; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> pp; int n,a[N],b[N]; int head[N],etot; struct Edge { int v,nxt; }e[N<<1]; int dis[N],siz[N],mx[N]; bool vis[N]; int ans; int root,s,sum; pp sta[N]; int tot; int used[N],cnt; int val[N]; inline void adde(int v,int u) { e[++etot].nxt=head[u],e[etot].v=v,head[u]=etot; } inline void smax(int &a,int b) { a=a>b?a:b; } inline int gcd(int a,int b) { return !b?a:gcd(b,a%b); } inline void getroot(int p,int fa) { mx[p]=-INF,siz[p]=1; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (vis[v]||v==fa) continue; getroot(v,p); siz[p]+=siz[v]; smax(mx[p],siz[v]); } smax(mx[p],sum-siz[p]); if (mx[p]<s) s=mx[p],root=p; } inline void getdis(int p,int fa) { b[p]=gcd(a[p],b[fa]); if (b[p]==1) return ; sta[++tot]=make_pair(b[p],dis[p]); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (vis[v]||v==fa) continue; dis[v]=dis[p]+1; getdis(v,p); } } inline void query(int x,int len) { for (int i=2;i*i<=x;++i) if (x%i==0) { while (x%i==0) x/=i; if (~val[i]) smax(ans,len+val[i]+1); } if (x^1&&~val[x]) smax(ans,len+val[x]+1); } inline void add(int x,int len) { for (int i=2;i*i<=x;++i) if (x%i==0) { while (x%i==0) x/=i; if (val[i]==-1) used[++cnt]=i; smax(val[i],len); } if (x^1) { if (val[x]==-1) used[++cnt]=x; smax(val[x],len); } } inline void calc(int p) { dis[p]=0; b[p]=a[p]; cnt=0; add(b[p],0); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (vis[v]) continue; dis[v]=1; tot=0; getdis(v,p); for (int j=1;j<=tot;++j) query(sta[j].first,sta[j].second); for (int j=1;j<=tot;++j) add(sta[j].first,sta[j].second); } for (register int i=1;i<=cnt;++i) val[used[i]]=-1; } inline void work(int p) { vis[p]=true; if (a[p]^1) calc(p); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (vis[v]) continue; s=INF,sum=siz[v]; getroot(v,0); work(root); } } inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } int main() { memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); memset(val,-1,sizeof(val)); n=read(); for (register int i=1;i<=n;++i) a[i]=read(); for (register int i=1;i<n;++i) { int u=read(),v=read(); adde(u,v); adde(v,u); } s=INF,sum=n; getroot(1,0); work(root); for (register int i=1;i<=n;++i) if (a[i]>1) smax(ans,1); printf("%d\n",ans); return 0; }
