几个月的坑终于补了……
题目大意：一棵 $n$ 个点的树，每个点有点权 $a_i$。一条路径的长度定义为该路径经过的点数。一条路径的权值定义为该路径经过所有点的点权的 GCD。问所有权值不为 $1$ 的路径中，最长的长度。
$1\le n\le 2\times 10^5,1\le a_i\le 2\times 10^5$。
我可能是数据结构学傻了，一眼点分治……然后复杂度又不对……
正解：我们发现只要 $\gcd$ 不为 $1$ 就行了，而两个数的 $\gcd$ 不为 $1$ 当且仅当他们两个有共有的质因子。
类比树的直径。每个点两个 vector，令 $pr[u]$ 表示 $a_u$ 的质因子集合（不重复），$len[u][i]$ 表示从 $u$ 向子树下面走，路径 $\gcd$ 含有 $a_u$ 的第 $i$ 个质因子的最长长度。
（有点说不清楚，看代码吧）
合并时与树的直径类似，就是拿一个子树和前面所有子树更新答案，再用这个子树更新 $u$ 点的 $len$。
具体看代码。时间复杂度 $O(n(\sqrt{a_i}+\log^2(a_i)))$。实际上会比这个上界小。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
char ch=getchar();int x=,f=;
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
int n,a[maxn],el,head[maxn],to[maxn*],nxt[maxn*],ans;
vector<int> pr[maxn],len[maxn];
inline void add(int u,int v){
to[++el]=v;nxt[el]=head[u];head[u]=el;
}
void dfs(int u,int f){
for(int i=;i*i<=a[u];i++)
if(a[u]%i==){
pr[u].push_back(i);
len[u].push_back();
ans=max(ans,);
while(a[u]%i==) a[u]/=i;
}
if(a[u]>) pr[u].push_back(a[u]),len[u].push_back(),ans=max(ans,);
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==f) continue;
dfs(v,u);
FOR(x,,(int)pr[u].size()-) FOR(y,,(int)pr[v].size()-){
if(pr[u][x]!=pr[v][y]) continue;
ans=max(ans,len[u][x]+len[v][y]);
len[u][x]=max(len[u][x],len[v][y]+);
}
}
}
int main(){
n=read();
FOR(i,,n) a[i]=read();
FOR(i,,n-){
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs(,);
printf("%d\n",ans);
}