HackerEarth XYZ Path queries problem solution YASH PAL, 31 July 2024 In this HackerEarth XYZ Path queries problem solution Given a tree with N nodes (numbered 1 to N). For each valid i, the i-th node has a value of A[i] associated with it. Your target is to handle the queries of the following 4 types – “1 X Y”: Sum of values of all the nodes in the path from X to Y. “2 X Y”: Sum of pairwise OR of every possible pair in the path from X to Y i.e. ∑(a[i] | a[j]) where i < j. “3 X Y”: Sum of OR of all triplet in the path from X to Y i.e. ∑(a[i] | a[j] | a[k]) where i < j < k. “4 X Y”: Sum of OR of all groups of type (a,b,c,d) in the path from X to Y i.e. ∑(a[i] | a[j] | a[k] | a[l]) where i < j < k < l. For each query answer can be very large so print it MODULO 1000000007 (1e9 + 7). HackerEarth XYZ Path queries problem solution. #include<bits/stdc++.h>using namespace std;#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define int long long int#define ll int#define bits_count __builtin_popcountll#define endl 'n'#define double long double#define ld double#define FOR(i,a,n) for (ll i=(a);i<=(n);++i)#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)#define ZERO(a) memset((a),0,sizeof((a)))#define MINUS(a) memset((a),-1,sizeof((a)))#define f first#define s second#define pb push_back#define mp make_pair#define all(g) g.begin(),g.end()#define sz(x) (ll)x.size()#define pr pair<int,int>int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; } // #include <ext/pb_ds/assoc_container.hpp> // Common file// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_updat// using namespace __gnu_pbds;// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();// struct chash { int operator()(int x) const { return x ^ RANDOM; }};// cc_hash_table<int, int, hash<int>> cnt;const int MOD = 1e9 + 7;const int MAXN = 1e5 + 10;const int LOG_A = 31;const int LEV = 19;vector<int> graph[MAXN];int a[MAXN][LOG_A];int dp[MAXN][LOG_A];int parent[MAXN][LEV];int level[MAXN];int fact[MAXN],invfact[MAXN];void dfs(int u,int p){ level[u] = level[p] + 1; parent[u][0] = p; // FOR DP (SET BITS SUMMATION FROM ROOT TO THAT NODE) FOR(i,0,LOG_A-1) dp[u][i] += dp[p][i]; FOR(i,0,LOG_A-1) dp[u][i] += a[u][i]; // FOR LCA CALCULATIOn FOR(lev,1,LEV-1){ parent[u][lev] = parent[parent[u][lev-1]][lev-1]; } for(int v:graph[u]){ if(v == p) continue; dfs(v,u); }}// STANDARD LCA CALCULATIONint lca_(int a,int b){ if(level[a] < level[b]) swap(a,b); int diff = level[a] - level[b]; FOR(i,0,LEV-1) if(diff&(1<<i)) a = parent[a][i]; if(a == b) return a; RFOR(i,0,LEV-1){ if(parent[a][i] != parent[b][i]){ a = parent[a][i]; b = parent[b][i]; } } return parent[a][0];}// POWER MODULOint power(int x,int y){ int res = 1; while(y){ if(y&1) res = (res*x)%MOD; x = (x*x)%MOD; y >>= 1; } return res;}// nCrint nCr(int n,int r){ if(r > n) return 0; int ret = (fact[n]*invfact[r])%MOD; return (ret*invfact[n-r])%MOD;}// FORMULA CALCULATION FOR EACH QUERYint return_statement(int type,int n,int m){ if(type == 1) { int ret = nCr(n,1); return ret; }else if(type == 2){ int ret = (nCr(n,2) + (nCr(n,1)*nCr(m,1)))%MOD; return ret; }else if(type == 3){ int ret1 = (nCr(n,3) + (nCr(n,2)*nCr(m,1)))%MOD; int ret2 = (nCr(n,1)*nCr(m,2))%MOD; return (ret1+ret2)%MOD; }else { int ret1 = (nCr(n,4) + (nCr(n,3)*nCr(m,1)))%MOD; int ret2 = ((nCr(n,2)*nCr(m,2)) + (nCr(n,1)*nCr(m,3)))%MOD; return (ret1+ret2)%MOD; }}void solve(){ fact[0] = 1; FOR(i,1,MAXN-1) fact[i] = (fact[i-1]*i)%MOD; FOR(i,0,MAXN-1) invfact[i] = power(fact[i],MOD-2); int n,q; cin>>n; FOR(i,1,n){ int x; cin>>x; FOR(bit,0,LOG_A-1){ if(x&(1LL<<bit)) a[i][bit] = 1; else a[i][bit] = 0; } } FOR(i,1,n-1){ int u,v; cin>>u>>v; graph[u].push_back(v); graph[v].push_back(u); } dfs(1,0); cin>>q; while(q--){ int type,x,y; cin>>type>>x>>y; int lca = lca_(x,y); int ans = 0; // GOING BITWISE FOR CALCULATION OF ANSWER FOR(bit,0,LOG_A-1){ int val = (1LL<<bit); int no_of_ones = (dp[y][bit] - dp[lca][bit]) + (dp[x][bit] - dp[lca][bit]) + a[lca][bit]; int no_of_zeros = level[x] + level[y] - 2*level[lca] + 1 - no_of_ones; ans = (ans + (val * return_statement(type,no_of_ones,no_of_zeros))%MOD)%MOD; } cout<<ans<<endl; }} signed main(){ FastRead; #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int t = 1; FOR(i,1,t){ solve(); }} coding problems