Educational Codeforces Round 58 (Rated for Div. 2) D.GCD Counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
D. GCD Counting
time limit per test4.5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a tree consisting of n vertices. A number is written on each vertex; the number on vertex i is equal to ai.
Let's denote the function g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices). Also let's denote dist(x,y) as the number of vertices on the simple path between vertices x and y, including the endpoints. dist(x,x)=1 for every vertex x.
Your task is calculate the maximum value of dist(x,y) among such pairs of vertices that g(x,y)>1.
Input
The first line contains one integer n — the number of vertices (1≤n≤2⋅105).
The second line contains n integers a1, a2, ..., an (1≤ai≤2⋅105) — the numbers written on vertices.
Then n−1 lines follow, each containing two integers x and y (1≤x,y≤n,x≠y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.
Output
If there is no pair of vertices x,y such that g(x,y)>1, print 0. Otherwise print the maximum value of dist(x,y) among such pairs.
Examples
inputCopy
3
2 3 4
1 2
2 3
outputCopy
1
inputCopy
3
2 3 4
1 3
2 3
outputCopy
2
inputCopy
3
1 1 1
1 2
2 3
outputCopy
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
#define ll __int64
const int maxn=2e5+10;
int n,a[maxn],vis[maxn],vis1[maxn],ans=1,flag=1,md,mp,p[maxn];
struct edge
{
int u,v;
edge(int uu,int vv):u(uu),v(vv){
}
};
vector<edge>e[maxn];
vector<int> v[maxn];
void dfs(int p,int d,int *vis)
{
if(vis[p])return;
vis[p]=1;
if(d>md)md=d,mp=p;
for(int i=0;i<v[p].size();++i)
dfs(v[p][i],d+1,vis);
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
for(ll i=2;i<maxn;++i)
{
if(!p[i])
{
for(ll j=i*i;j<maxn;j+=i)
p[j]=1;
}
}
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i),a[i]>1&&(flag=0);//短路判均<=1
}
if(flag)
{
puts("0");
return 0;
}
for(int i=1;i<n;++i)
{
int u,v,k;
scanf("%d%d",&u,&v);
if((k=gcd(a[u],a[v]))>1)
{
for(int j=1;j*j<=k;++j)//j从1开始是为了判k
{
if(k%j==0)
{
if(!p[j]&&j!=1)e[j].push_back(edge(u,v));
if(j*j!=k&&!p[k/j])e[k/j].push_back(edge(u,v));
}
}
}
}
for(int i=2;i<maxn;++i)
{
if(!p[i])
{
vector<int> p;
for(int j=0;j<e[i].size();++j)
{
edge& E=e[i][j];
p.push_back(E.u);
p.push_back(E.v);
v[E.u].push_back(E.v);
v[E.v].push_back(E.u);
}
for(int j=0;j<p.size();++j)
{
vis[p[j]]=vis1[p[j]]=0;
}
for(int j=0;j<p.size();++j)
{
if(!vis[p[j]])
{
md=0;
dfs(p[j],1,vis);
md=0;
dfs(mp,1,vis1);
ans=max(ans,md);
}
}
for(int j=0;j<p.size();++j)
v[p[j]].clear();
}
}
printf("%dn",ans);
return 0;
}