GCD Counting【Educational Codeforces Round 58 (Rated for Div. 2) 1101D】【树的直径 + 质数筛】题目链接

74 阅读 0 评论 49 点赞

我是靠谱客的博主朴实向日葵，最近开发中收集的这篇文章主要介绍GCD Counting【Educational Codeforces Round 58 (Rated for Div. 2) 1101D】【树的直径 + 质数筛】题目链接，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

D. GCD Counting

time limit per test

4.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard 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. ????(?,?)=1dist(x,x)=1 for every vertex ?x.

Your task is calculate the maximum value of ????(?,?)dist(x,y) among such pairs of vertices that ?(?,?)>1g(x,y)>1.

Input

The first line contains one integer ?n — the number of vertices (1≤?≤2⋅105)(1≤n≤2⋅105).

The second line contains ?n integers ?1a1, ?2a2, ..., ??an (1≤??≤2⋅105)(1≤ai≤2⋅105) — the numbers written on vertices.

Then ?−1n−1 lines follow, each containing two integers ?x and ?y (1≤?,?≤?,?≠?)(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 ?(?,?)>1g(x,y)>1, print 00. Otherwise print the maximum value of ????(?,?)dist(x,y) among such pairs.

Examples

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

output

Copy

题意：求一条gcd不为1的最长的链的长度。

思路：处理这样的一条链，说明这条链上的每个点都有一个相同的质因子，那不如就用这质因子去跑通过这个节点来跑这棵树，我们假设这条链都是以这个质因子为基础跑出来的，然后，就是质因子内存所有的节点，若是跑过的话，就说明已经是跑过该子树的树的直径了，就不需要进去跑了，否则，就是把这点放进去跑树的直径即可，然后每次ans更新最大的树的直径即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, a[maxN], head[maxN], cnt;
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN<<2];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
bool is_Prim[maxN], vis[maxN];
//vis用来记忆化是否走过的点
unordered_set<int> son[maxN], prim[maxN];
inline void Prim_deal() //质数筛
{
memset(is_Prim, true, sizeof(is_Prim));
is_Prim[0] = is_Prim[1] = false;
for(int i=2; i<maxN; i++)
{
if(is_Prim[i])
{
for(int j=2*i; j<maxN; j+=i)
{
is_Prim[j] = false;
son[j].insert(i);
}
son[i].insert(i);
}
}
}
int max_line_len, pos_st;
//此时取到的最大的链长，目的在于找到起始点pos_st
inline void dfs1(int u, int fa, int len, int gcd)
//gcd是此时处理的以gcd为公共质因子，我们最远走到的距离的点
{
if(vis[u]) return;
vis[u] = true;
if(len > max_line_len)
{
max_line_len = len;
pos_st = u;
}
for(int i=head[u]; i!=-1; i=edge[i].nex)
{
int v = edge[i].to;
if(v == fa || son[a[v]].find(gcd) == son[a[v]].end() || vis[v]) continue;
dfs1(v, u, len+1, gcd);
}
}
int tree_len;
//此时求的树的直径
inline void dfs2(int u, int fa, int len, int gcd)
{
if(len > tree_len) tree_len = len;
for(int i=head[u]; i!=-1; i=edge[i].nex)
{
int v = edge[i].to;
if(v == fa || son[a[v]].find(gcd) == son[a[v]].end()) continue;
dfs2(v, u, len+1, gcd);
}
}
inline void init()
{
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
cnt = 0;
}
int main()
{
Prim_deal();
init();
scanf("%d", &N);
for(int i=1; i<=N; i++)
{
scanf("%d", &a[i]);
for(auto j=son[a[i]].begin(); j!=son[a[i]].end(); j++) prim[*j].insert(i);
}
for(int i=1; i<N; i++)
{
int e1, e2;
scanf("%d%d", &e1, &e2);
addEddge(e1, e2);
addEddge(e2, e1);
}
int ans = 0;
for(int i=2; i<maxN; i++)
{
if(is_Prim[i])
{
memset(vis, false, sizeof(vis));
for(auto j=prim[i].begin(); j!=prim[i].end(); j++)
{
max_line_len = tree_len = 0;
dfs1(*j, -1, 1, i);
if(max_line_len) dfs2(pos_st, -1, 1, i);
ans = max(ans, tree_len);
}
}
}
printf("%dn", ans);
return 0;
}