Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth XOR in Tree problem solution

YASH PAL, 31 July 2024
In this HackerEarth XOR in Tree problem In Graph theory, tree is a simple connected acyclic graph. You are given a tree consists of N nodes numbered from 1 to N. Each node i have a value Ai associated with it. Your task is writing a program doing Q operations, each operations is 1 of 2 following types:
  1. u, v: Assign Au to v.
  2. u, v: Calculate XOR sum of all value associated with nodes in unique single path from u to v.
HackerEarth XOR in Tree problem solution

HackerEarth XOR in Tree problem solution.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000 + 10;
const int MAXL = 22;

vector<int> adj[MAXN];
int a[MAXN], subtree[MAXN], pos[MAXN], path_xor[MAXN], depth[MAXN];
int par[MAXN][MAXL];
bool visited[MAXN];
int n, m, l;

void DFS(int u) {
visited[u] = true;
subtree[u] = 1;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!visited[v]) {
path_xor[v] = path_xor[u] ^ a[v]; depth[v] = depth[u] + 1;
DFS(v);
subtree[u] += subtree[v]; par[v][0] = u;
}
}
pos[u] = m; m--;
}

void init() {
scanf("%dn", &n);
assert((1 <= n) && (n <= 100000));
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
assert((1 <= a[i]) && (a[i] <= (int)(1e9)));
adj[i].clear();
}
for(int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d %dn", &u, &v);
assert((1 <= u) && (u <= n));
assert((1 <= v) && (v <= n));
adj[u].push_back(v); adj[v].push_back(u);
}
for(int i = 1; i <= n; i++) visited[i] = false;
m = n;
path_xor[1] = a[1]; depth[1] = 0;
DFS(1);
l = (int)(log(n) / log(2)) + 1;
for(int j = 1; j <= l; j++) {
for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];
}
}

struct segment_tree {
int T[8 * MAXN];
int n;

void init(int _n) {
n = _n;
for(int i = 0; i <= 8 * n; i++) T[i] = 0;
}

void lazy_propagation(int node, int from, int to) {
if (from < to) {
T[node * 2] ^= T[node]; T[node * 2 + 1] ^= T[node];
T[node] = 0;
}
}

void update(int node, int from, int to, int l, int r, int val) {
lazy_propagation(node, from, to);
if ((from > r) || (to < l)) return;
if ((from >= l) && (to <= r)) {
T[node] ^= val;
return;
}
int mid = (from + to) / 2;
update(node * 2, from, mid, l, r, val);
update(node * 2 + 1, mid + 1, to, l, r, val);
}

void get_val(int node, int from, int to, int pos, int &result) {
lazy_propagation(node, from, to);
if ((from > pos) || (to < pos)) return;
if (from == to) {
result = T[node];
return;
}
int mid = (from + to) / 2;
get_val(node * 2, from, mid, pos, result);
get_val(node * 2 + 1, mid + 1, to, pos, result);
}

void xor_range(int l, int r, int val) {
update(1, 1, n, l, r, val);
}

int get_xor(int x) {
int res = 0;
get_val(1, 1, n, x, res);
return res;
}

} ST;

void jump(int &u, int height) {
for(int i = l; i >= 0; i--) {
if (height >= (1 << i)) {
u = par[u][i];
height -= (1 << i);
}
}
}

int lca(int u, int v) {
if (depth[u] > depth[v]) jump(u, depth[u] - depth[v]); else jump(v, depth[v] - depth[u]);
if (u == v) return(u);
for(int i = l; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
u = par[u][i]; v = par[v][i];
}
}
return par[u][0];
}

int main()
{
int test_cases;
cin >> test_cases;
while (test_cases --) {
init();
int q;
scanf("%dn", &q);
assert((1 <= q) && (q <= 100000));
ST.init(n);
for(int i = 1; i <= q; i++) {
int t, u, v;
scanf("%d %d %dn", &t, &u, &v);
assert((1 <= t) && (t <= 2));
assert((1 <= u) && (u <= n));
if (t == 1) {
assert((1 <= v) && (v <= (int)(1e9)));
ST.xor_range(pos[u], pos[u] + subtree[u] - 1, a[u] ^ v);
a[u] = v;
}
else {
assert((1 <= v) && (v <= n));
int c = lca(u, v);
int res = path_xor[u] ^ path_xor[v] ^ ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c];
printf("%dn", res);
}
}
}
}

Second solution

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct To {
typedef int Vertex;
Vertex to;
To() { }
To(Vertex to_): to(to_) { }
};

template<typename To_>
struct StaticGraph {
typedef To_ To;
typedef typename To::Vertex Vertex;
typedef std::pair<Vertex,To> Edge;
typedef const To *const_iterator;

void init(int n_, const std::vector<Edge> &edges) {
n = n_; int m = edges.size();
tos.resize(m+1); offsets.resize(n+1);
for(int e = 0; e < m; e ++) offsets[edges[e].first] ++;
for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1];
for(int e = 0; e < m; e ++)
tos[-- offsets[edges[e].first]] = edges[e].second;
}
int numVertices() const { return n; }
int numEdges() const { return tos.size() - 1; }

inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; }
inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; }
private:
int n;
std::vector<To> tos;
std::vector<int> offsets;
};


class SchieberVishkinLCA {
public:
typedef StaticGraph<To> Graph;
typedef unsigned Word;
typedef Graph::Vertex Vertex;
private:

static inline Word lowestOneBit(Word v) {
return v & (~v+1);
}
static inline Word highestOneBitMask(Word v) {
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return v >> 1;
}

std::vector<Word> indices;
std::vector<Word> maxHIndices;
std::vector<Word> ancestorHeights;
std::vector<Vertex> pathParents;
public:
void build(const Graph &g, Vertex root) {
return build(g, std::vector<Vertex>(1, root));
}
void build(const Graph &g, const std::vector<Vertex> &roots) {
int N = g.numVertices();

ancestorHeights.resize(N);
std::vector<Vertex> parents(N);
maxHIndices.resize(N);
std::vector<Vertex> vertices; vertices.reserve(N);
indices.resize(N);

Word currentIndex = 1;
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
parents[root] = root;
vertices.push_back(root);
}
while(!vertices.empty()) {
Vertex v = vertices.back(); vertices.pop_back();
indices[v] = currentIndex ++;
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it) {
parents[it->to] = v;
vertices.push_back(it->to);
}
}

int head = 0, tail = roots.size();
vertices.resize(N);
for(int ri = 0; ri < (int)roots.size(); ri ++)
vertices[ri] = roots[ri];
while(head != tail) {
Vertex v = vertices[head ++];
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it)
vertices[tail ++] = it->to;
}

for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it)
maxHIndices[*it] = indices[*it];
for(std::vector<Vertex>::const_reverse_iterator it = vertices.rbegin(); it != vertices.rend(); ++ it) {
Vertex v = *it, parent = parents[v];
if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
maxHIndices[parent] = maxHIndices[v];
}

for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
ancestorHeights[root] = 0;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
}

pathParents.swap(parents);
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
pathParents[indices[root]-1] = root;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
for(const Graph::To *jt = g.edgesBegin(v); jt != g.edgesEnd(v); ++ jt) {
if(maxHIndices[v] != maxHIndices[jt->to])
pathParents[indices[jt->to]-1] = v;
else
pathParents[indices[jt->to]-1] = pathParents[indices[v]-1];
}
}
}

Vertex query(Vertex v, Vertex u) const {
Word Iv = maxHIndices[v], Iu = maxHIndices[u];
Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
Vertex x, y;
if(j == hIv) x = v;
else {
Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1));
x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];
}
if(j == hIu) y = u;
else {
Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1));
y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];
}
return indices[x] < indices[y] ? x : y;
}
};



vector<int> t_parent;
vi t_seq; vector<bool> t_sign;
vector<int> t_left, t_right;

void tree_signedeulertour(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_left.assign(n, -1);
t_right.assign(n, -1);
t_seq.assign(n * 2, -1);
t_sign.assign(n * 2, false);
int pos = 0;

vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
if(i < 0) {
i = -i - 1;
t_seq[pos] = i;
t_sign[pos] = true;
pos ++;
t_right[i] = pos;
continue;
}
t_left[i] = pos;
t_seq[pos] = i;
t_sign[pos] = false;
pos ++;

stk.push_back(-(i+1));
for(int j = (int)g[i].size()-1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root)
stk.push_back(c);
else
t_parent[i] = c;
}
}
}

struct FenwickTreeXor {
typedef int T;
vector<T> v;
void init(int n) { v.assign(n, 0); }
void add(int i, T x) {
for(; i < (int)v.size(); i |= i+1) v[i] ^= x;
}
T sum(int i) const {
T r = 0;
for(-- i; i >= 0; i = (i & (i+1)) - 1) r ^= v[i];
return r;
}
T sum(int left, int right) const {
return sum(right) ^ sum(left);
}
};


int main() {
typedef SchieberVishkinLCA::Graph Graph;

int T;
scanf("%d", &T);
assert(1 <= T && T <= 10);
rep(ii, T) {
int N;
scanf("%d", &N);
assert(1 <= N && N <= 100000);
vector<int> A(N);
rep(i, N) {
scanf("%d", &A[i]);
assert(1 <= A[i] && A[i] <= 1000000000);
}
vector<vi> g(N);
rep(i, N-1) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
assert(0 <= u && u < N && 0 <= v && v < N);
g[u].push_back(v);
g[v].push_back(u);
}
tree_signedeulertour(g, 0);

vector<Graph::Edge> edges;
reu(i, 1, N)
edges.push_back(Graph::Edge(t_parent[i], i));
Graph gg; gg.init(N, edges);
SchieberVishkinLCA lca; lca.build(gg, 0);

FenwickTreeXor ft;
ft.init(t_seq.size());
rep(i, t_seq.size())
ft.add(i, A[t_seq[i]]);

int Q;
scanf("%d", &Q);
assert(1 <= Q && Q <= 100000);
rep(jj, Q) {
int t;
scanf("%d", &t);
assert(1 <= t && t <= 2);
if(t == 1) {
int u, v;
scanf("%d%d", &u, &v), -- u;
assert(0 <= u && u < N);
assert(1 <= v && v <= 1000000000);
ft.add(t_left[u], A[u] ^ v);
ft.add(t_right[u] - 1, A[u] ^ v);
A[u] = v;
}else if(t == 2) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
assert(0 <= u && u < N && 0 <= v && v < N);
int w = lca.query(u, v);
int ans = 0;
ans ^= ft.sum(t_left[w], t_left[u] + 1);
ans ^= ft.sum(t_left[w] + 1, t_left[v] + 1);
printf("%dn", ans);
}
}
}
return 0;
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes