# HackerEarth Skrtel ! problem solution

In this HackerEarth Skrtel ! problem solution Stevie : "The more you play with Christmas Trees, the more addicted you are to them. Let's go on". Legends serve a club selflessly for ages without any noise off the pitch. Do you remember the headed goal vs the Gunners with a highly bandaged head by this guy : ?
You are given a Tree T consisting of N nodes where node i of the tree has number A[i] written on it. Now, you need to process 2 kinds of queries on this tree.
1.  X Y : Update the number written on node with index X to Y
2.  U V K : Find if the product of number written on each nodes lying on the path from node U to V is divisible by the number K.
The answer to the second kind of query is either a YES or NO .

## HackerEarth Skrtel ! problem solution.

`import java.io.*;import java.util.*;import java.math.*;public final class solution{    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));    static FastScanner sc=new FastScanner(br);    static PrintWriter out=new PrintWriter(System.out);    static Random rnd=new Random();    static int[][] al;    static int[] x,y,a,tin,tout,sp,cnt;    static int[][] st;    static int maxn=(int)(2e5+5);    static int time=0;    static int LN=21;    static Map<Integer,Integer> m1;    static ArrayList<Node>[] events;    static Map<Integer,Integer>[] mp;    static int[] bit;    static void put(int idx,int val)    {        m1.put(idx,m1.getOrDefault(idx,0)+val);    }        static void build()    {        sp=new int[maxn];                for(int i=2;i<maxn;i++)        {            if(sp[i]==0)            {                for(int j=i;j<maxn;j+=i)                {                    sp[j]=i;                }            }        }    }        static void dfs(int u,int p)    {        tin[u]=++time;st[0][u]=p;                for(int x:al[u])        {            if(x!=p)            {                dfs(x,u);            }        }                tout[u]=time;    }        static void update(int idx,int val)    {        while(idx<maxn)        {            bit[idx]+=val;idx+=idx&-idx;        }    }        static int query(int idx)    {        int ret=0;                while(idx>0)        {            ret=ret+bit[idx];idx-=idx&-idx;        }                return ret;    }        static void clear(int idx)    {        while(idx<maxn)        {            bit[idx]=0;idx+=idx&-idx;        }    }        static void solve(int num)    {        for(Node x:events[num])        {            if(x.a==1)            {                update(x.b,x.d);update(x.c,-x.d);            }                        else            {                int curr=query(x.c)+query(x.d)-query(x.e)-(x.f==-1?0:query(x.f));                                mp[x.b].put(num,mp[x.b].get(num)-curr);            }        }                for(Node x:events[num])        {            if(x.a==1)            {                clear(x.b);clear(x.c);            }        }    }        static boolean isAncestor(int u,int v)    {        return (tin[u]<=tin[v] && tout[u]>=tout[v]);    }        static int lca(int u,int v)    {        if(isAncestor(u,v)) return u;                if(isAncestor(v,u)) return v;                for(int i=LN-1;i>=0;i--)        {            if(!isAncestor(st[i][u],v))            {                u=st[i][u];            }        }                return st[0][u];    }        @SuppressWarnings("unchecked")    public static void run() throws Exception    {        build();int n=sc.nextInt(),q=sc.nextInt();a=new int[n];cnt=new int[n];                if(n<1 || n>100000 || q<1 || q>100000) throw new Exception("Wrong");                for(int i=0;i<n;i++)        {            a[i]=sc.nextInt();                        if(a[i]<=1 && a[i]>200000) throw new Exception("Wrong");        }                x=new int[n];y=new int[n];                for(int i=1;i<n;i++)        {            x[i]=sc.nextInt()-1;y[i]=sc.nextInt()-1;                        cnt[x[i]]++;cnt[y[i]]++;                        if(x[i]>=y[i]) throw new Exception("Wrong");        }                al=new int[n][];bit=new int[maxn];                for(int i=0;i<n;i++)        {            al[i]=new int[cnt[i]];cnt[i]=0;        }                for(int i=1;i<n;i++)        {            al[x[i]][cnt[x[i]]++]=y[i];                        al[y[i]][cnt[y[i]]++]=x[i];        }                tin=new int[n];tout=new int[n];st=new int[LN][n];dfs(0,0);                for(int i=1;i<LN;i++)        {            for(int j=0;j<n;j++)            {                st[i][j]=st[i-1][st[i-1][j]];            }        }                events=new ArrayList[maxn];                for(int i=1;i<maxn;i++)        {            events[i]=new ArrayList<Node>();        }                for(int i=0;i<n;i++)        {            m1=new HashMap<>();int curr=a[i];                        while(curr>1)            {                put(sp[curr],1);curr/=sp[curr];            }                        for(Map.Entry<Integer,Integer> en:m1.entrySet())            {                int key=en.getKey();                                events[key].add(new Node(1,tin[i],tout[i]+1,en.getValue(),-1,-1));            }        }                mp=new HashMap[q];                for(int i=0;i<q;i++)        {            mp[i]=new HashMap<Integer,Integer>();        }                for(int i=0;i<q;i++)        {            int t=sc.nextInt();                        if(t==1)            {                int x=sc.nextInt()-1;m1=new HashMap<>();                                if(x<0 || x>=n) throw new Exception("Wrong");                                int curr=a[x];                                while(curr>1)                {                    put(sp[curr],1);curr/=sp[curr];                }                                for(Map.Entry<Integer,Integer> en:m1.entrySet())                {                    int key=en.getKey();                                        events[key].add(new Node(1,tin[x],tout[x]+1,-en.getValue(),-1,-1));                }                                a[x]=sc.nextInt();curr=a[x];m1=new HashMap<>();                                if(curr<=1 && curr>200000) throw new Exception("Wrong");                                while(curr>1)                {                    put(sp[curr],1);curr/=sp[curr];                }                                for(Map.Entry<Integer,Integer> en:m1.entrySet())                {                    int key=en.getKey();                                        events[key].add(new Node(1,tin[x],tout[x]+1,en.getValue(),-1,-1));                }               }                        else            {                int u=sc.nextInt()-1,v=sc.nextInt()-1,k=sc.nextInt(),lca=lca(u,v);                                if(u<0 || u>=n || v<0 || v>=n || k<=1 || k>200000)  throw new Exception("Wrong");                                int curr=k;m1=new HashMap<>();                                while(curr>1)                {                    put(sp[curr],1);curr/=sp[curr];                }                                for(Map.Entry<Integer,Integer> en:m1.entrySet())                {                    int key=en.getKey();                                        events[key].add(new Node(2,i,tin[u],tin[v],tin[lca],lca==0?-1:tin[st[0][lca]]));                }                                mp[i]=new HashMap<>(m1);            }        }            for(int i=2;i<maxn;i++)        {            solve(i);        }                for(int i=0;i<q;i++)        {            if(mp[i].size()!=0)            {                boolean ans=true;                for(Map.Entry<Integer,Integer> en:mp[i].entrySet())                {                    if(en.getValue()>0)                    {                        ans=false;break;                    }                }                out.println(ans?"YES":"NO");            }        }                out.close();    }        public static void main(String[] args) throws Exception    {        new Thread(null,new Runnable(){            public void run()            {                try                {                    new solution().run();                }                catch(Exception e)                {                                    }            }        },"1",1<<28).start();    }}class Node{    int a,b,c,d,e,f;        public Node(int a,int b,int c,int d,int e,int f)    {        this.a=a;this.b=b;this.c=c;this.d=d;this.e=e;this.f=f;    }}class FastScanner{    BufferedReader in;    StringTokenizer st;    public FastScanner(BufferedReader in) {        this.in = in;    }        public String nextToken() throws Exception {        while (st == null || !st.hasMoreTokens()) {            st = new StringTokenizer(in.readLine());        }        return st.nextToken();    }        public String next() throws Exception {        return nextToken().toString();    }        public int nextInt() throws Exception {        return Integer.parseInt(nextToken());    }    public long nextLong() throws Exception {        return Long.parseLong(nextToken());    }    public double nextDouble() throws Exception {        return Double.parseDouble(nextToken());    }}`

### Second solution

`#include <iostream>#include <vector>#include <algorithm>#include <cstring>using namespace std;typedef pair<int,int> pii;const int LGN = 18;const int MAXN = 200005;struct event{    int type, v1, v2, val, index;    event(int a, int b, int c)    {        type = 1;        v1 = b;        v2 = -1;        val = c;        index = a;    }    event(int a, int b, int c, int d)    {        type = 2;        v1 = b;        v2 = c;        val = d;        index = a;    }};bool sieve[MAXN], ans[MAXN];int curr_time, factor[MAXN], cval[MAXN], depth[MAXN], BIT[MAXN], subtree_start[MAXN], subtree_end[MAXN], par[MAXN][LGN];vector <int> G[MAXN];vector <event> to_process[MAXN];vector <pii> factorise(int x){    vector <pii> ret;    while(x > 1)    {        int ctr = 0, cfact = factor[x];        while(factor[x] == cfact)        {            ctr++;            x/=cfact;        }        ret.push_back(pii(cfact,ctr));    }    return ret;}void BIT_upd(int pos, int val){    while(pos < MAXN)    {        BIT[pos]+=val;        pos+=(pos & (-pos));    }}int BIT_get(int pos){    int ret = 0;    while(pos > 0)    {        ret+=BIT[pos];        pos-=(pos & (-pos));    }    return ret;}void add_val_to_subtree(int root, int val){    BIT_upd(subtree_start[root], val);    BIT_upd(subtree_end[root]+1, -val);}int get_path_val(int pos){    return BIT_get(subtree_start[pos]);}void dfs(int pos, int prev){    par[pos][0] = prev;    depth[pos] = depth[prev] + 1;    curr_time++;    subtree_start[pos] = curr_time;    for (int i = 0; i < G[pos].size(); ++i)    {        if(G[pos][i] != prev)            dfs(G[pos][i],pos);    }    subtree_end[pos] = curr_time;}int lca(int u, int v){    if(depth[u] < depth[v])        swap(u,v);    int diff = depth[u] - depth[v];    for (int i = 0; i < LGN; ++i)    {        if(diff & (1<<i))            u = par[u][i];    }    if(u == v)        return u;    for (int i = LGN - 1; i >= 0; --i)    {        if(par[u][i] != par[v][i])        {            u = par[u][i];            v = par[v][i];        }    }    return par[u][0];}int main(){    for (int i = 2; i < MAXN; ++i)    {        if(!sieve[i])        {            for (int j = i; j < MAXN; j+=i)            {                factor[j] = i;                sieve[j] = true;            }        }    }    int n,q;    cin>>n>>q;    for (int i = 1; i <= n; ++i)    {        int x;        cin>>x;        cval[i] = x;        vector <pii> pfact = factorise(x);        for (int j = 0; j < pfact.size(); ++j)        {            int p = pfact[j].first, c = pfact[j].second;            to_process[p].push_back(event(0,i,c));        }    }    for (int i = 0; i < n - 1; ++i)    {        int u,v;        cin>>u>>v;        G[u].push_back(v);        G[v].push_back(u);    }    vector <int> queries;    for (int i = 1; i <= q; ++i)    {        int ty;        cin>>ty;        if(ty == 1)        {            int x,y;            cin>>x>>y;            vector <pii> oldfact = factorise(cval[x]);            for (int j = 0; j < oldfact.size(); ++j)            {                int p = oldfact[j].first;                to_process[p].push_back(event(i,x,0));            }            cval[x] = y;            vector <pii> pfact = factorise(y);            for (int j = 0; j < pfact.size(); ++j)            {                int p = pfact[j].first, c = pfact[j].second;                to_process[p].push_back(event(i,x,c));            }        }        else        {            int u,v,k;            cin>>u>>v>>k;            vector <pii> pfact = factorise(k);            for (int j = 0; j < pfact.size(); ++j)            {                int p = pfact[j].first, c = pfact[j].second;                to_process[p].push_back(event(i,u,v,c));            }            queries.push_back(i);        }        ans[i] = true;    }    dfs(1,0);    for (int j = 1; j < LGN; ++j)    {        for (int i = 1; i <= n; ++i)        {            par[i][j] = par[par[i][j-1]][j-1];        }    }    memset(cval, 0, sizeof cval);    for (int p = 2; p < MAXN; ++p)    {        vector <int> changed;        for (int i = 0; i < to_process[p].size(); ++i)        {            int ty = to_process[p][i].type;            if(ty == 1)            {                int set_to = to_process[p][i].val;                int node = to_process[p][i].v1;                int curr_val = cval[node];                add_val_to_subtree(node,set_to-curr_val);                cval[node] = set_to;                changed.push_back(node);            }            else            {                int u = to_process[p][i].v1, v = to_process[p][i].v2;                int l = lca(u,v);                int path_sum = get_path_val(u) + get_path_val(v) - get_path_val(l) - get_path_val(par[l][0]);                if(path_sum < to_process[p][i].val)                    ans[to_process[p][i].index] = false;            }        }        sort(changed.begin(), changed.end());        changed.resize(unique(changed.begin(), changed.end()) - changed.begin());        for (int i = 0; i < changed.size(); ++i)        {            add_val_to_subtree(changed[i], -cval[changed[i]]);            cval[changed[i]] = 0;        }    }    for (int i = 0; i < queries.size(); ++i)    {        if(ans[queries[i]])            cout<<"YES\n";        else            cout<<"NO\n";    }    return 0;}`