CodeForces - 1101D：GCD Counting （树分治）

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

Input

Output

Input

Output

Input

Output

题意：让你求最长的路径长度，满足路上gcd不为1；

思路：分治的做法比较暴力，但是时限比较长，有板子就直接上了。由于gcd具有收敛性，路径上的gcd不会太多，而且越远回越接近1，我们记录每一个gcd的最深的位置即可。（我用的以前的板子，所以用了map，此题的数据量可以不用map

还有一个思路，我们枚举素因子，然后把含有这个素因子的点标记出来，求他们的最远距离，更新答案。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

const int inf=0x7FFFFFFF;

int Laxt[maxn],Next[maxn<<],To[maxn<<],cnt,N,sn;

int a[maxn],sz[maxn],son[maxn],vis[maxn],root,res;

int dep[maxn];

ll ans[maxn];

map<int,int>mp,tp;

map<int,int>::iterator it1,it2;

inline void read(int &x) {

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c<=''&&c>='') x=(x<<)+(x<<)+c-'',c=getchar();

}

void add(int u,int v){

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt; To[cnt]=v;

}

void getroot(int u,int fa) //找重心

{

    sz[u]=; son[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        if(To[i]!=fa&&!vis[To[i]]){

            getroot(To[i],u);

            sz[u]+=sz[To[i]];

            son[u]=max(son[u],sz[To[i]]);

        }

    }

    son[u]=max(son[u],sn-son[u]);

    if(root==||son[root]>son[u]) root=u;

}

void getans(int u,int fa,int num) //对于当前链产生的新GCD

{

    dep[u]=dep[fa]+; tp[num]=max(tp[num],dep[u]);

    for(int i=Laxt[u];i;i=Next[i]){

        if(!vis[To[i]]&&To[i]!=fa){

            getans(To[i],u,__gcd(num,a[To[i]]));

        }

    }

}

void solve(int u) //解决以u为根的子问题

{

    mp.clear(); mp[a[u]]=; ans[a[u]]++; dep[u]=;

    for(int i=Laxt[u];i;i=Next[i])

      if(!vis[To[i]]) {

         tp.clear(); getans(To[i],u,__gcd(a[u],a[To[i]]));

         for(it1=mp.begin();it1!=mp.end();it1++)

           for(it2=tp.begin();it2!=tp.end();it2++){

              int g=__gcd((*it1).first,(*it2).first);

              if(g>) res=max(res,(*it1).second+(*it2).second-);

        }

        for(it2=tp.begin();it2!=tp.end();it2++)

          mp[(*it2).first]=max((*it2).second,mp[(*it2).first]);

    }

}

void dfs(int u)  //分治

{

    vis[u]=;  solve(u);

    for(int i=Laxt[u];i;i=Next[i]){

        if(vis[To[i]]) continue;

        root=; sn=sz[To[i]];

        getroot(To[i],); dfs(root);

    }

}

int main()

{

    read(N); int u,v,Max=;

    for(int i=;i<=N;i++) read(a[i]),Max=max(Max,a[i]);

    for(int i=;i<N;i++) {

        read(u);read(v);

        add(u,v);  add(v,u);

    }

    if(Max>) res=;

    root=; sn=N; getroot(,); dfs(root);

    printf("%d\n",res);

    return ;

}

秒客网

CodeForces - 1101D：GCD Counting （树分治）

相关文章