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:
- u, v: Assign Au to v.
- 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.
#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("%d\n", &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 %d\n", &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("%d\n", &q);
assert((1 <= q) && (q <= 100000));
ST.init(n);
for(int i = 1; i <= q; i++) {
int t, u, v;
scanf("%d %d %d\n", &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("%d\n", 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("%d\n", ans);
}
}
}
return 0;
}
0 Comments