HackerEarth Path queries problem solution YASH PAL, 31 July 2024 In this HackerEarth Path queries problem solution, You are given an undirected tree G with N nodes. Every node is assigned a value denoted by . A simple path u1 – u2 – u3 – u4,…, -uk is said to be beautiful if the number of pairs of nodes (ui, ui+1) where A[ui] is odd and A[ui + 1] is even and number of pairs of nodes (ui, ui+1) where A[ui] is even and A[ui + 1] is odd are equal. Given Q queries of the form: u val: Set the value of node n equal to val, i.e. set A[u] = val and find the number of ordered pairs (u,v) such that the simple path between node u and node v is beautiful. hackerEarth Path queries problem solution. #include<bits/stdc++.h>#define int long long intusing namespace std;void solve(){ int n, q; cin >> n >> q; assert(1 <= n and n <= 200000); assert(1 <= q and q <= 200000); int a[n + 1]; int c_e = 0; int c_o = 0; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; assert(1 <= a[i] and a[i] <= 1000000000); if(a[i]%2) c_o++; else c_e++; } for(int i = 1 ; i <= n - 1 ; i++){ int u, v; cin >> u >> v; assert(1 <= u and u <= n); assert(1 <= v and v <= n); assert(u != v); } while(q--) { int u, val; cin >> u >> val; assert(1 <= u and u <= n); assert(1 <= val and val <= 1000000000); if(a[u]%2) c_o--; else c_e--; a[u] = val; if(a[u]%2) c_o++; else c_e++; int answer = (c_e*(c_e - 1))/2; answer += (c_o*(c_o - 1))/2; answer += (c_o + c_e); cout << answer << " "; } cout << endl;}signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; assert(1 <= t and t <= 10); while(t--){ solve(); }} coding problems