codeforces1101D.GCD Counting 数论+DP+dfs

81 阅读 0 评论 54 点赞

我是靠谱客的博主清脆大雁，最近开发中收集的这篇文章主要介绍codeforces1101D.GCD Counting 数论+DP+dfs，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 nn vertices. A number is written on each vertex; the number on vertex ii is equal to aiai .

Let's denote the function g(x,y)g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex xx to vertex yy (including these two vertices). Also let's denote dist(x,y)dist(x,y) as the number of vertices on the simple path between vertices xx and yy , including the endpoints. dist(x,x)=1dist(x,x)=1 for every vertex xx .

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

Input

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

The second line contains nn integers a1a1 , a2a2 , ..., anan (1≤ai≤2⋅105)(1≤ai≤2⋅105) — the numbers written on vertices.

Then n−1n−1 lines follow, each containing two integers xx and yy (1≤x,y≤n,x≠y)(1≤x,y≤n,x≠y) denoting an edge connecting vertex xx with vertex yy . It is guaranteed that these edges form a tree.

Output

If there is no pair of vertices x,yx,y such that g(x,y)>1g(x,y)>1 , print 00 . Otherwise print the maximum value of dist(x,y)dist(x,y) among such pairs.

Examples

Input

Copy

Output

Copy

Input

Copy

Output

Copy

Input

Copy

Output

Copy

题意：给你一颗树，每一个树上有其权值，dist(x,y)为两点间的短距离，g(x,y)为两点间的gcd没让你求最长的dist（x，y）且g(x,y)>1.

思路：因为要求的的是gcd大于1，所以只要有相同的不为1的因子就可以满足条件，所以我们就先把这每个点的权值的因子找出来，在树上dfs，搜索当前根节点下的每个因子的dist，根据下一个节点相同因子的找最大值，一直取最大值。

代码：

#include<stdio.h>
#include<string.h>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<iterator>
#include<set>
#include<map>
#include<bitset>
#include<complex>
#define ll long long
#define qq printf("QAQn");
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const double e=exp(1.0);
const double pi=acos(-1);
const double eps=1e-6;
int a[maxn],ans;
map<int,int>mp[maxn];
vector<int>fac[maxn];
void get_div(int x)
{
int temp=a[x];
for(int i=2;i*i<=temp;i++)
{
if(temp%i==0){
fac[x].push_back(i);
while(temp%i==0)temp/=i;
}
}
if(temp!=1)fac[x].push_back(temp);
}
vector<int>v[maxn];
void dfs(int st,int fa)
{
for(int i=0;i<fac[st].size();i++)//先每个点的每个因子初始化为1
mp[st][fac[st][i]]=1;
for(int i=0;i<v[st].size();i++)
{
int next=v[st][i];
if(next==fa)continue;
dfs(next,st);
for(int j=0;j<fac[st].size();j++)//遍历每个节点的因子
{
int div=fac[st][j];
mp[st][div]=max(mp[st][div],mp[next][div]+1);//最大长度
ans=max(ans,mp[st][div]);
for(int k=0;k<i;k++)
{
ans=max(ans,mp[next][div]+mp[v[st][k]][div]+1);//两个分支 可以够成最大的
}
}
}
}
int main()
{
int n,st,en;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
get_div(i);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&st,&en);
v[st].push_back(en);
v[en].push_back(st);
}
ans=0;
dfs(1,-1);//因为是把1这个因子不考虑，不用特判0
printf("%dn",ans);
return 0;
}