Description：

给一棵树，每个点有权值，找一条最长的权值 $\gcd$ 不为 $1$ 的路径。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

实际上只要这条路径所有权值都有一个公共质因子就行了，考虑点分治，同时维护一个 $g[]$ 表示每个质因子到分治重心的最远距离，然后就是一个简单的路径统计了，分解质因数可以线性筛预处理 $mindiv$ 然后就是不超过 $\log n$ 个，用的 $map$ 所以是 $n\log^3n$ 。

Code：

#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 200010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int mindiv[MAXN];

void sieve()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mindiv[1] = 1;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])prime[++tot] = i,mindiv[i] = i;

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

int v[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int root,s,siz[MAXN],d[MAXN];

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!vis[e[i].to] && e[i].to != fa)

		{

			getroot(e[i].to,k);

			siz[k] += siz[e[i].to];

			d[k] = max(d[k],siz[e[i].to]);

		}

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

map<int,int> g;

int ans = -1;

void query(int val,int dis)

{

	while(val != 1)

	{

		int k = mindiv[val];

		if(g.find(k) != g.end())ans = max(ans,g[k] + dis);

		while(val % k == 0)val /= k;

	}

	return;

}

void insert(int val,int dis)

{

	while(val != 1)

	{

		int k = mindiv[val];

		g[k] = max(g[k],dis);

		while(val % k == 0)val /= k;

	}

	return;

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

void calc(int k,int fa,int val,int dis)

{

	val = gcd(val,v[k]);

	query(val,dis);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		calc(e[i].to,k,val,dis + 1);

	}

	return;

}

void get(int k,int fa,int val,int dis)

{

	val = gcd(val,v[k]);

	insert(val,dis);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		get(e[i].to,k,val,dis + 1);

	}

	return;

}

void divide(int k)

{

	vis[k] = true;

	g.clear();

	insert(v[k],0);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		calc(e[i].to,k,v[k],1);

		get(e[i].to,k,v[k],1);

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		s = siz[e[i].to];root = 0;

		getroot(e[i].to,k);

		divide(root);

	}

	return;

}

int main()

{

	cin >> n;

	sieve();

	for(int i = 1;i <= n;++i)cin >> v[i];

	for(int i = 1;i <= n;++i)if(v[i] != 1)ans = 0;

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	root = 0;s = n;d[0] = INF;

	getroot(1,0);

	divide(root);

	cout << ans + 1 << endl;

	return 0;

}