# HackerEarth GCD Path on a Tree problem solution

In this HackerEarth GCD Path on a Tree problem solution Given an Integer K and a tree of N vertices where each vertex consists of a value Vi associated to it. Find the longest path in the tree which satisfies the following conditions

The number of vertices in the path should be a multiple of K.
Let's say there are L X K vertices in the path and Xi be the value associated with ith vertex in that path, then gcd(X(iXK+1), X(iXK+2), X(iXK+3), ... X(iXK+K)) > 1 for all i belongs to [0,L - 1] where gcd(x1,x2...xn) is the Greatest Common Divisor of the numbers x1,x2...xn.

## HackerEarth GCD Path on a Tree problem solution.

`#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef double D;typedef vector<int> VI;typedef vector<ll> VL;typedef pair<int,int> PII;typedef pair<ll,ll> PLL;#define rd(x) scanf("%d",&x)#define rd2(x,y) scanf("%d %d",&x,&y)#define rl(x) scanf("%lld",&x)#define rl2(x,y) scanf("%lld %lld",&x,&y)#define wd(x) printf("%d" ,x)#define wd2(x,y) printf("%d %d",x,y)#define wl(x) printf("%lld",x)#define wl2(x,y) printf("%lld %lld",x,y)#define PC(x) putchar(x)#define GC() getchar()#define NL printf("\n")#define SP printf(" ")#define F first#define S second#define MP make_pair#define PB push_back#define fr(i,s,e) for(int i=s;i<e;i++)#define frr(i,s,e) for(int i=s-1;i>=e;i--)#define frv(i,a) for(int i = 0;i<(int)a.size();i++)#define frvr(i,a) for(int i = a.size()-1;i>=0;i--)#define tr(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end();i++)#ifdef LOCAL#define E1(a) cout<<#a<<":" <<a<<endl;#define E2(a,b) cout<<#a<<":" <<a<<" " <<#b<<":" <<b<<endl;#define E3(a,b,c) cout<<#a<<":" <<a<<" " <<#b<<":" <<b<<" "<<#c<<":"<<c<<endl;#define E4(a,b,c,d) cout<<#a<<":" <<a<<" " <<#b<<":" <<b<<" "<<#c<<":"<<c<< " "<<#d<< ":"<<d<<endl;#define INP freopen("input","r",stdin);#define OUT freopen("output","w",stdout);#else#define E1(a)#define E2(a,b)#define E3(a,b,c)#define E4(a,b,c,d)#define INP#define OUT#endif#define mod 1000000007#define maxn 100009#define maxr 1000009int n,k,ans,val[maxn],mx[maxn];VI pf[maxr],al[maxn];map<int,VI > dp[maxn];void primeFactors(vector<int> v[],int n){    for(int i=2;i<=n;i++){        if(v[i].empty()){            for(int j=i;j<=n;j+=i){                v[j].push_back(i);            }        }    }}bool inline check(int v,int p,int m){    if(dp[v].find(p)==dp[v].end()||dp[v][p][m]==-1)return 0;    return 1;}void calc(int v,int p){    map<int,VI> bst_mp;    int bst = 0;    VI &factors = pf[val[v]];    mx[v] = 0;    frv(i,factors){        int prime = factors[i];        dp[v][prime] = vector<int>(k+1,-1);        bst_mp[prime] = vector<int>(k+1,-1);        dp[v][prime][1] = 1;        if(k==1){dp[v][prime][k] = mx[v] = 1;}    }    frv(i,al[v]){        int u = al[v][i];        if(u==p)continue;        frv(j,factors){            int prime = factors[j];            dp[v][prime][1] = max(dp[v][prime][1],mx[u]+1);            for(int m=2;m<=k;m++){                if(!check(u,prime,m-1))continue;                dp[v][prime][m] = max(dp[v][prime][m],dp[u][prime][m-1]+1);            }            mx[v] = max(mx[v],dp[v][prime][k]);        }        if(k==1){ans = max(ans,bst+1+mx[u]);}        else{            frv(j,factors){                int prime = factors[j];                if(bst_mp[prime][k-1]!=-1){ans = max(ans,bst_mp[prime][k-1]+1+mx[u]);}                if(check(u,prime,k-1)){ans = max(ans,bst+1+dp[u][prime][k-1]);}                for(int m=1;m<=k-2;m++){                    if(bst_mp[prime][k-m-1]!=-1&&check(u,prime,m)){                        ans = max(ans,bst_mp[prime][k-m-1]+1+dp[u][prime][m]);                    }                }            }            frv(j,factors){                int prime = factors[j];                for(int m=1;m<=k;m++){                    if(check(u,prime,m))bst_mp[prime][m] = max(bst_mp[prime][m],dp[u][prime][m]);                }            }        }        bst = max(bst,mx[u]);    }    ans = max(ans,mx[v]);}void dfs(int v,int p){    frv(i,al[v]){        int u = al[v][i];        if(u==p)continue;        dfs(u,v);    }    calc(v,p);}int main(){    for(int i=0;i<maxr;i++)pf[i].clear();    primeFactors(pf,maxr-1);    cin>>n>>k;    for(int i=0;i<=n;i++)al[i].clear();    for(int i=0;i<n-1;i++){        int u,v;        rd2(u,v);        al[u].PB(v);        al[v].PB(u);    }    for(int i=1;i<=n;i++)rd(val[i]);    ans = 0;    dfs(1,0);    cout<<ans<<endl;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define ll long long#define sd(x) scanf("%d", &(x))#define F first#define S secondconst int K = 12;const int N = 1e5 +10, M = 1e6 + 10;vector<int> primedivs[M];vector<int> con[N];int prime[M], val[N], parent[N];void pre(){    for(int i = 2; i * i < M; i++)        for(int j = i * i; j < M; j += i) prime[j] = 1;    for(int i = 2; i < M; i++){        if(!prime[i])            for(int j = i; j < M; j += i) primedivs[j].push_back(i);    }}int n, k;int ans = 0;vector<int> dp[K];int maxlen[N], vis[N], dist[N];void go(int init, int s, int p = 0, int d = 1, int g = 0){    if(d == k + 1){        maxlen[init] = max(maxlen[init], k + maxlen[s]);        return;    }    g =__gcd(g, val[s]);    if(g == 1) return;    if(d == k){        maxlen[init] = max(maxlen[init], k);    }    for(int v : con[s]){        if(v != p){            go(init, v, s, d + 1, g);        }    }}void getmaxlen(int s = 1, int p = 0){    parent[s] = p;    for(int v : con[s]){        if(v != p){            getmaxlen(v, s);        }    }    go(s, s, p);    ans = max(ans, maxlen[s]);}const int INF = 1e6;void go2(int init, int s, int p, int par = 0, int d = 1){    if(d == 2){        for(int i = 1; i <= k; i++) dp[i].push_back(-INF);    }    if(d >= 2) dp[d - 1].back() = max(dp[d - 1].back(), maxlen[s]);    if(d == k + 1){        return;    }    if(val[s] % p != 0) return;    if(d >= 2 && (d == k || (s != 1 && con[s].size() == 1))){        dp[d].back() = max(dp[d].back(), 0);    }       for(int v : con[s]){        if(v != par){            go2(init, v, p, s, d + 1);        }    }}int getMax(int s){    int ans2 = 0;    for(int p : primedivs[val[s]]){        for(int i = 1; i <= k; i++) dp[i].clear();        go2(s, s, p, parent[s]);        vector<int> currMax(K, -INF);        for(int i = 0; i < dp[1].size(); i++){            for(int l1 = 1; l1 <= k; l1++){                int l2 = k + 1 - l1;                ans2 = max(ans2, k + currMax[l2] + dp[l1][i]);            }            for(int l1 = 1; l1 <= k; l1++) currMax[l1] = max(currMax[l1], dp[l1][i]);        }    }    ans = max(ans, ans2);}int main(){    pre();    sd(n); sd(k);    int u, v;    for(int i = 1; i < n; i++){        sd(u);        sd(v);        con[u].push_back(v);        con[v].push_back(u);    }    for(int i = 1; i <= n; i++){        val[i] = 720720;        sd(val[i]);    }    getmaxlen();    for(int i = 1; i <= n; i++){        getMax(i);    }    printf("%d\n", ans);}`