HackerEarth Skrtel ! problem solution YASH PAL, 31 July 2024 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. X Y : Update the number written on node with index X to Y 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<<"YESn"; else cout<<"NOn"; } return 0;} coding problems