304 North Cardinal St.
Dorchester Center, MA 02124

# Pishty and tree CodeChef Solution

## Pishty and tree CodeChef Solution in C++17

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

static struct FastInput {
static constexpr int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
size_t buf_pos = 0;
FILE *in = stdin;
char cur = 0;

inline char get_char() {
buf_pos = 0;
buf[0] = (chars_read == 0 ? -1 : buf[0]);
}
return cur = buf[buf_pos++];
}

inline void tie(int) {}

inline explicit operator bool() {
return cur != -1;
}

inline static bool is_blank(char c) {
return c <= ' ';
}

inline bool skip_blanks() {
while (is_blank(cur) && cur != -1) {
get_char();
}
return cur != -1;
}

inline FastInput& operator>>(char& c) {
skip_blanks();
c = cur;
return *this;
}

inline FastInput& operator>>(string& s) {
if (skip_blanks()) {
s.clear();
do {
s += cur;
} while (!is_blank(get_char()));
}
return *this;
}

template <typename T>
// unsafe, doesn't check that characters are actually digits
n = 0;
if (skip_blanks()) {
int sign = +1;
if (cur == '-') {
sign = -1;
get_char();
}
do {
n += n + (n << 3) + cur - '0';
} while (!is_blank(get_char()));
n *= sign;
}
return *this;
}

template <typename T>
inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
}

#if !defined(_WIN32) | defined(_WIN64)
inline FastInput& operator>>(__int128& n) {
}
#endif

template <typename T>
inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
// not sure if really fast, for compatibility only
n = 0;
if (skip_blanks()) {
string s;
(*this) >> s;
sscanf(s.c_str(), "%lf", &n);
}
return *this;
}
} fast_input;

#define cin fast_input

static struct FastOutput {
static constexpr int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
size_t buf_pos = 0;
static constexpr int TMP_SIZE = 1 << 20;
char tmp[TMP_SIZE];
FILE *out = stdout;

inline void put_char(char c) {
buf[buf_pos++] = c;
if (buf_pos == BUF_SIZE) {
fwrite(buf, 1, buf_pos, out);
buf_pos = 0;
}
}

~FastOutput() {
fwrite(buf, 1, buf_pos, out);
}

inline FastOutput& operator<<(char c) {
put_char(c);
return *this;
}

inline FastOutput& operator<<(const char* s) {
while (*s) {
put_char(*s++);
}
return *this;
}

inline FastOutput& operator<<(const string& s) {
for (int i = 0; i < (int) s.size(); i++) {
put_char(s[i]);
}
return *this;
}

template <typename T>
inline char* integer_to_string(T n) {
// beware of TMP_SIZE
char* p = tmp + TMP_SIZE - 1;
if (n == 0) {
*--p = '0';
} else {
bool is_negative = false;
if (n < 0) {
is_negative = true;
n = -n;
}
while (n > 0) {
*--p = (char) ('0' + n % 10);
n /= 10;
}
if (is_negative) {
*--p = '-';
}
}
return p;
}

template <typename T>
inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
return integer_to_string(n);
}

#if !defined(_WIN32) || defined(_WIN64)
inline char* stringify(__int128 n) {
return integer_to_string(n);
}
#endif

template <typename T>
inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
sprintf(tmp, "%.17f", n);
return tmp;
}

template <typename T>
inline FastOutput& operator<<(const T& n) {
auto p = stringify(n);
for (; *p != 0; p++) {
put_char(*p);
}
return *this;
}
} fast_output;
#define cout fast_output

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}

const int N = 1e5 + 4;
int n, m;

int dep[N], par[N];
int sz[N], heavy[N];
void dfs(int u, int p) {
sz[u] = 1; heavy[u] = -1;
for (int v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}

int timer;
void dfs_hld(int u, int top) {
pos[u] = ++timer;

if (heavy[u] != -1) {
dfs_hld(heavy[u], top);
for (int v: adj[u]) if (v != par[u] && v != heavy[u]) dfs_hld(v, v);
}
}

int ans[N];
int numQuery;
struct Query {
int k, u, v, id;
bool operator< (const Query &other) const {
if (k != other.k) return k < other.k;
return id < other.id;
}
} q[N << 1];

int st[N << 2];
void build(int id, int l, int r) {
if (l == r) st[id] = 0;
else {
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] ^ st[id << 1 | 1];
}
}

void update(int id, int l, int r, int u, int v) {
if (l == r) st[id] = v;
else {
int mid = l + r >> 1;
if (u <= mid) update(id << 1, l, mid, u, v);
else update(id << 1 | 1, mid + 1, r, u, v);
st[id] = st[id << 1] ^ st[id << 1 | 1];
}
}

void update(int u, int v) {
update(1, 1, n, u, v);
}

int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
else {
int mid = l + r >> 1;
return get(id << 1, l, mid, u, v) ^ get(id << 1 | 1, mid + 1, r, u, v);
}
}

int get(int u, int v) {
int res = 0;
res ^= get(1, 1, n, pos[head[u]], pos[u]);
}
if (dep[u] < dep[v]) swap(u, v); // u la con cua v
int oldV = get(1, 1, n, pos[v], pos[v]);
res ^= get(1, 1, n, pos[v], pos[u]) ^ oldV; return res;
}

main() {
int t; cin >> t;
while (t--) {
cin >> n;
numQuery = 0;
build(1, 1, n);
for (int i = 1, u, v, c; i < n; ++i) {
cin >> u >> v >> c;
q[++numQuery] = {c, u, v, 0};
}
timer = 0;
dfs(1, -1);
dfs_hld(1, 1);
cin >> m;
for (int i = 1; i <= m; ++i) {
int u, v, k; cin >> u >> v >> k;
q[++numQuery] = {k, u, v, i};
}
sort(q + 1, q + 1 + numQuery);
for (int i = 1; i <= numQuery; ++i) {
int k = q[i].k, u = q[i].u, v = q[i].v, id = q[i].id;
if (id == 0) {
if (pos[u] < pos[v]) swap(u, v);
update(pos[u], k);
} else ans[id] = get(u, v);
}
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
for (int i = 1; i <= n; ++i) adj[i].clear();
}
}``````

## Pishty and tree CodeChef Solution in C++14

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

static struct FastInput {
static constexpr int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
size_t buf_pos = 0;
FILE *in = stdin;
char cur = 0;

inline char get_char() {
buf_pos = 0;
buf[0] = (chars_read == 0 ? -1 : buf[0]);
}
return cur = buf[buf_pos++];
}

inline void tie(int) {}

inline explicit operator bool() {
return cur != -1;
}

inline static bool is_blank(char c) {
return c <= ' ';
}

inline bool skip_blanks() {
while (is_blank(cur) && cur != -1) {
get_char();
}
return cur != -1;
}

inline FastInput& operator>>(char& c) {
skip_blanks();
c = cur;
return *this;
}

inline FastInput& operator>>(string& s) {
if (skip_blanks()) {
s.clear();
do {
s += cur;
} while (!is_blank(get_char()));
}
return *this;
}

template <typename T>
// unsafe, doesn't check that characters are actually digits
n = 0;
if (skip_blanks()) {
int sign = +1;
if (cur == '-') {
sign = -1;
get_char();
}
do {
n += n + (n << 3) + cur - '0';
} while (!is_blank(get_char()));
n *= sign;
}
return *this;
}

template <typename T>
inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
}

#if !defined(_WIN32) | defined(_WIN64)
inline FastInput& operator>>(__int128& n) {
}
#endif

template <typename T>
inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
// not sure if really fast, for compatibility only
n = 0;
if (skip_blanks()) {
string s;
(*this) >> s;
sscanf(s.c_str(), "%lf", &n);
}
return *this;
}
} fast_input;

#define cin fast_input

static struct FastOutput {
static constexpr int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
size_t buf_pos = 0;
static constexpr int TMP_SIZE = 1 << 20;
char tmp[TMP_SIZE];
FILE *out = stdout;

inline void put_char(char c) {
buf[buf_pos++] = c;
if (buf_pos == BUF_SIZE) {
fwrite(buf, 1, buf_pos, out);
buf_pos = 0;
}
}

~FastOutput() {
fwrite(buf, 1, buf_pos, out);
}

inline FastOutput& operator<<(char c) {
put_char(c);
return *this;
}

inline FastOutput& operator<<(const char* s) {
while (*s) {
put_char(*s++);
}
return *this;
}

inline FastOutput& operator<<(const string& s) {
for (int i = 0; i < (int) s.size(); i++) {
put_char(s[i]);
}
return *this;
}

template <typename T>
inline char* integer_to_string(T n) {
// beware of TMP_SIZE
char* p = tmp + TMP_SIZE - 1;
if (n == 0) {
*--p = '0';
} else {
bool is_negative = false;
if (n < 0) {
is_negative = true;
n = -n;
}
while (n > 0) {
*--p = (char) ('0' + n % 10);
n /= 10;
}
if (is_negative) {
*--p = '-';
}
}
return p;
}

template <typename T>
inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
return integer_to_string(n);
}

#if !defined(_WIN32) || defined(_WIN64)
inline char* stringify(__int128 n) {
return integer_to_string(n);
}
#endif

template <typename T>
inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
sprintf(tmp, "%.17f", n);
return tmp;
}

template <typename T>
inline FastOutput& operator<<(const T& n) {
auto p = stringify(n);
for (; *p != 0; p++) {
put_char(*p);
}
return *this;
}
} fast_output;
#define cout fast_output

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}

const int N = 1e5 + 4;
int n, m;

int dep[N], par[N];
int sz[N], heavy[N];
void dfs(int u, int p) {
sz[u] = 1; heavy[u] = -1;
for (int v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}

int timer;
void dfs_hld(int u, int top) {
pos[u] = ++timer;

if (heavy[u] != -1) {
dfs_hld(heavy[u], top);
for (int v: adj[u]) if (v != par[u] && v != heavy[u]) dfs_hld(v, v);
}
}

int ans[N];
int numQuery;
struct Query {
int k, u, v, id;
bool operator< (const Query &other) const {
if (k != other.k) return k < other.k;
return id < other.id;
}
} q[N << 1];

int st[N << 2];
void build(int id, int l, int r) {
if (l == r) st[id] = 0;
else {
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] ^ st[id << 1 | 1];
}
}

void update(int id, int l, int r, int u, int v) {
if (l == r) st[id] = v;
else {
int mid = l + r >> 1;
if (u <= mid) update(id << 1, l, mid, u, v);
else update(id << 1 | 1, mid + 1, r, u, v);
st[id] = st[id << 1] ^ st[id << 1 | 1];
}
}

void update(int u, int v) {
update(1, 1, n, u, v);
}

int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
else {
int mid = l + r >> 1;
return get(id << 1, l, mid, u, v) ^ get(id << 1 | 1, mid + 1, r, u, v);
}
}

int get(int u, int v) {
int res = 0;
res ^= get(1, 1, n, pos[head[u]], pos[u]);
}
if (dep[u] < dep[v]) swap(u, v); // u la con cua v
int oldV = get(1, 1, n, pos[v], pos[v]);
res ^= get(1, 1, n, pos[v], pos[u]) ^ oldV; return res;
}

main() {
int t; cin >> t;
while (t--) {
cin >> n;
numQuery = 0;
build(1, 1, n);
for (int i = 1, u, v, c; i < n; ++i) {
cin >> u >> v >> c;
q[++numQuery] = {c, u, v, 0};
}
timer = 0;
dfs(1, -1);
dfs_hld(1, 1);
cin >> m;
for (int i = 1; i <= m; ++i) {
int u, v, k; cin >> u >> v >> k;
q[++numQuery] = {k, u, v, i};
}
sort(q + 1, q + 1 + numQuery);
for (int i = 1; i <= numQuery; ++i) {
int k = q[i].k, u = q[i].u, v = q[i].v, id = q[i].id;
if (id == 0) {
if (pos[u] < pos[v]) swap(u, v);
update(pos[u], k);
} else ans[id] = get(u, v);
}
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
for (int i = 1; i <= n; ++i) adj[i].clear();
}
}``````

## Pishty and tree CodeChef Solution in C

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLOCK 444
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void dfs(int x,int y);
int get_i(int*a,int num,int size);
int med(int*a,int size);
void sort_a(int*a,int size,int*new_size);
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size);
void clean_table();
void insert_edge(int x,int y,int w);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
int c,x[100000],y[100000],z[100000],q1[200000],q2[200000],qt[200000],idx[200000],sort_k[100000],track[100000],trace[200000],number[100000],ans[200000];
lnode *table[100000];

int main(){
int T,N,M,size,u,v,k,p1,p2,r,i;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(i=0;i<N-1;i++){
scanf("%d%d%d",x+i,y+i,z+i);
x[i]--;
y[i]--;
sort_k[i]=z[i];
}
sort_a(sort_k,N-1,&size);
memset(track,0,sizeof(track));
for(i=0;i<N-1;i++)
insert_edge(x[i],y[i],get_i(sort_k,z[i],size));
c=0;
dfs(0,-1);
scanf("%d",&M);
for(i=0;i<M;i++){
scanf("%d%d%d",&u,&v,&k);
q1[2*i]=number[u-1];
q1[2*i+1]=number[v-1];
qt[2*i]=number[u-1]/BLOCK;
qt[2*i+1]=number[v-1]/BLOCK;
q2[2*i]=q2[2*i+1]=get_i(sort_k,k+1,size);
idx[2*i]=2*i;
idx[2*i+1]=2*i+1;
}
sort_a3(qt,q2,idx,2*M);
for(i=p1=p2=r=0;i<2*M;i++){
while(q2[i]>p2){
if(track[p2])
r^=sort_k[p2];
p2++;
}
while(q2[i]<p2){
p2--;
if(track[p2])
r^=sort_k[p2];
}
while(q1[idx[i]]>p1){
if(trace[p1]<q2[i])
r^=sort_k[trace[p1]];
track[trace[p1]]^=1;
p1++;
}
while(q1[idx[i]]<p1){
p1--;
if(trace[p1]<q2[i])
r^=sort_k[trace[p1]];
track[trace[p1]]^=1;
}
ans[idx[i]]=r;
}
for(i=0;i<M;i++)
printf("%d\n",(ans[2*i]^ans[2*i+1]));
clean_table();
}
return 0;
}
void dfs(int x,int y){
lnode *p;
number[x]=c;
for(p=table[x];p;p=p->next)
if(p->x!=y){
trace[c++]=p->w;
dfs(p->x,x);
trace[c++]=p->w;
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
void sort_a(int*a,int size,int*new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
int new_l_size=0,new_r_size=0;
sort_a(left,m,&new_l_size);
sort_a(right,size-m,&new_r_size);
merge(a,left,right,new_l_size,new_r_size,new_size);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[index++] = right[j];
j++;
} else if (j == right_size) {
a[index++] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[index++] = left[i];
i++;
} else {
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
index--;
}
(*new_size)=index;
return;
}
void clean_table(){
int i;
lnode *p,*pp;
for(i=0;i<100000;i++)
if(table[i]){
p=table[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
table[i]=NULL;
}
return;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] < right_a[j] || (left_a[i]==right_a[j] && left_b[i]<right_b[j])) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}``````

## Pishty and tree CodeChef Solution in JAVA

``````import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
OutputWriter out = new OutputWriter(outputStream);
PishtyAndTree solver = new PishtyAndTree();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}

static class PishtyAndTree {
int[] tin;
int[] tout;
int[] e;
int count;
int n;
int m;
ArrayList<Edge>[] g;
int[] par;
boolean[] vis;
ArrayList<Edge> edges;
ArrayList<Edge> queries;

public void solve(int testNumber, InputReader in, OutputWriter out) {
pre(in);
count = 0;
tin = new int[n];
tout = new int[n];
e = new int[2 * n];
int q = in.nextInt();
for (int i = 0; i < q; i++) {
queries.add(new Edge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt(), i));
}
Collections.sort(queries);
Collections.sort(edges);
dfs(0, -1);
int j = 0;
ST s = new ST(0, 2 * n - 1, e);
int[] ans = new int[q];

for (Edge ed : queries) {
//            out.println(ed.from,ed.node,ed.id,ed.cost);
while (j < n - 1 && edges.get(j).cost <= ed.cost) {
Edge te = edges.get(j);
int x = 0;
if (par[te.from] == te.node) {
x = te.from;
} else {
x = te.node;
}
//                out.println(x,tin[x],tout[x]);
s.update(tin[x], edges.get(j).cost);
s.update(tout[x], edges.get(j).cost);
j++;
}
//            out.println(tin[ed.from],tin[ed.node],ed.id);
int val = s.query(0, tin[ed.from]) ^ s.query(0, tin[ed.node]);
ans[ed.id] = val;
}
for (int a : ans) {
out.println(a);
}

}

void dfs(int nn, int pp) {
par[nn] = pp;
tin[nn] = count++;
for (Edge a : g[nn]) {
if (a.node == pp) continue;
dfs(a.node, nn);
}
tout[nn] = count++;
}

n = in.nextInt();
m = n - 1;
g = new ArrayList[n];
par = new int[n];
vis = new boolean[n];
edges = new ArrayList<>();
queries = new ArrayList<>();
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
}
}

class ST {
int leftmost;
int rightmost;
ST lchild;
ST rchild;
int sum;

public ST(int leftmost, int rightmost, int[] a) {
this.leftmost = leftmost;
this.rightmost = rightmost;
if (leftmost == rightmost) {
//leaf
sum = a[leftmost];
} else {
// 2 children
int mid = (leftmost + rightmost) / 2;
// (l,mid) (mid+1,r)
lchild = new ST(leftmost, mid, a);
rchild = new ST(mid + 1, rightmost, a);
recalc();
}
}

public void recalc() {
if (leftmost == rightmost) return;
sum = lchild.sum ^ rchild.sum;
}

public void update(int index, int newVal) {
if (leftmost == rightmost) {
//leaf;
sum = newVal;
} else {
// 2 children
if (index <= lchild.rightmost) lchild.update(index, newVal);
else rchild.update(index, newVal);
recalc();
}
}

public int query(int l, int r) {
// entirely disjoint
if (l > rightmost || r < leftmost) return 0;
// covers us
if (l <= leftmost && r >= rightmost) return sum;
// we don't know
return lchild.query(l, r) ^ rchild.query(l, r);
}

}

class Edge implements Comparable<Edge> {
int from;
int node;
int cost;
int id;

Edge(int x, int a, int b, int id) {
from = x;
node = a;
cost = b;
this.id = id;
}

public int compareTo(Edge e) {
return cost - e.cost;
}

}

}

static class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void close() {
writer.close();
}

public void println(int i) {
writer.println(i);
}

}

StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

public int nextInt() {
return Integer.parseInt(next());
}

}
}
``````

## Pishty and tree CodeChef Solution in C#

``````using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

// (づ°ω°)づﾐe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
public class Solver
{
class Bit
{

public Bit(int n)
{
size = n;
data = new int[n];
}

public int PrefixSum(int r)
{
int ret = 0;
for (; r >= 0; r = (r & r + 1) - 1)
ret ^= data[r];
return ret;
}

public void Update(int idx, int diff)
{
for (; idx < size; idx = (idx | idx + 1))
data[idx] ^= diff;
}
}

List<Tuple<int, int>>[] g;
int timer;
int[] tin, tout;

void Dfs1(int x, int p)
{
tin[x] = timer++;
foreach (var e in g[x])
if (e.Item1 != p)
Dfs1(e.Item1, x);
tout[x] = timer++;
}

public void Solve()
{
for (int tt = ReadInt(); tt > 0; tt--)
{

g = Init<List<Tuple<int, int>>>(n);
var ed = new int[n - 1][];
for (int i = 1; i < n; i++)
{
int u = ReadInt() - 1;
int v = ReadInt() - 1;
ed[i - 1] = new []{ u, v, w };
}
Array.Sort(ed, (e1, e2) => e1[2].CompareTo(e2[2]));

timer = 0;
tin = new int[n];
tout = new int[n];
Dfs1(0, -1);

var a = new int[q][];
for (int i = 0; i < q; i++)
{
int u = ReadInt() - 1;
int v = ReadInt() - 1;
a[i] = new [] { u, v, w, i };
}

Array.Sort(a, (a1, a2) => a1[2].CompareTo(a2[2]));
var bit = new Bit(2 * n);
int p = 0;
var ans = new int[q];
for (int i = 0; i < q; i++)
{
while (p < n - 1 && ed[p][2] <= a[i][2])
{
int x;
if (tin[ed[p][0]] < tin[ed[p][1]])
x = ed[p][1];
else
x = ed[p][0];
bit.Update(tin[x], ed[p][2]);
bit.Update(tout[x], ed[p][2]);
p++;
}
ans[a[i][3]] = bit.PrefixSum(tin[a[i][0]]) ^ bit.PrefixSum(tin[a[i][1]]);
}

WriteLines(ans);
}
}

#region Main

protected static TextWriter writer;
static void Main()
{
#if DEBUG
writer = Console.Out;
//writer = new StreamWriter("..\\..\\output.txt");
#else
writer = new StreamWriter(Console.OpenStandardOutput());
//writer = new StreamWriter("output.txt");
#endif
try
{
new Solver().Solve();
}
catch (Exception ex)
{
#if DEBUG
Console.WriteLine(ex);
#else
throw;
#endif
}
writer.Close();
}

#endregion

private static Queue<string> currentLineTokens = new Queue<string>();
public static string ReadToken() { while (currentLineTokens.Count == 0)currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }
{
int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++)ret[i][j] = matrix[j][i]; } return ret;
}
public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++)lines[i] = reader.ReadLine().Trim(); return lines; }
public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
public static void Write(params object[] array) { WriteArray(array); }
public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array)writer.WriteLine(a); }
private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
public new TValue this[TKey key]
{
get { return ContainsKey(key) ? base[key] : default(TValue); }
set { base[key] = value; }
}
}
private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++)ret[i] = new T(); return ret; }
#endregion
}``````

## Pishty and tree CodeChef Solution in GO

``````package main

import (
"bufio"
"fmt"
"os"
"sort"
)

func readInt(bytes []byte, from int, val *int) int {
i := from
tmp := 0
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp
return i
}

func readNum(scanner *bufio.Scanner) (a int) {
scanner.Scan()
return
}

func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
scanner.Scan()
return
}

func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
}
return res
}

func main() {
scanner := bufio.NewScanner(os.Stdin)

for tc > 0 {
edges := make([][]int, n-1)
for i := 0; i < n-1; i++ {
}
queries := make([][]int, Q)
for i := 0; i < Q; i++ {
}
res := solve(n, edges, Q, queries)

for _, ans := range res {
fmt.Println(ans)
}

tc--
}
}

func solve(n int, edges [][]int, Q int, queries [][]int) []int {
neighbors := make([]map[int]int, n)
for i := 0; i < n; i++ {
neighbors[i] = make(map[int]int)
}

for _, edge := range edges {
u, v, c := edge[0]-1, edge[1]-1, edge[2]
neighbors[u][v] = c
neighbors[v][u] = c
}

st := make([]int, n)
ed := make([]int, n)

var dfs func(p, u int, time *int)

dfs = func(p, u int, time *int) {
(*time)++
st[u] = *time
for v := range neighbors[u] {
if v == p {
continue
}
dfs(u, v, time)
}
ed[u] = *time
}
dfs(0, 0, new(int))

ps := make(Pairs, 0, 2*n)
for i := 0; i < n-1; i++ {
u, v, c := edges[i][0]-1, edges[i][1]-1, edges[i][2]
if st[u] < st[v] {
u, v = v, u
}
u++
// make sure u is larger than 0
ps = append(ps, Pair{c, -u})
}

for i := 0; i < Q; i++ {
k := queries[i][2]
ps = append(ps, Pair{k, i})
}

res := make([]int, Q)
sort.Sort(ps)
bit := CreateBit(n)
for i := 0; i < len(ps); i++ {
p := ps[i]
if p.second < 0 {
node := -p.second
node--
} else {
idx := p.second
u, v := queries[idx][0]-1, queries[idx][1]-1
res[idx] = bit.Get(st[u]) ^ bit.Get(st[v])
}
}

return res
}

type BIT struct {
arr  []int
size int
}

func CreateBit(n int) BIT {
arr := make([]int, n+1)
return BIT{arr, n}
}

func (bit *BIT) Add(x, v int) {
for x <= bit.size {
bit.arr[x] ^= v
x += x & (-x)
}
}

func (bit BIT) Get(x int) int {
var ans int
for x > 0 {
ans ^= bit.arr[x]
x -= x & (-x)
}
return ans
}

type Pair struct {
first, second int
}

type Pairs []Pair

func (ps Pairs) Len() int {
return len(ps)
}

func (ps Pairs) Less(i, j int) bool {
return ps[i].first < ps[j].first || ps[i].first == ps[j].first && ps[i].second < ps[j].second
}

func (ps Pairs) Swap(i, j int) {
ps[i], ps[j] = ps[j], ps[i]
}

const MAX_LEVEL = 21

func solve1(n int, edges [][]int, Q int, queries [][]int) []int {
neighbors := make([]map[int]int, n)
for i := 0; i < n; i++ {
neighbors[i] = make(map[int]int)
}

for _, edge := range edges {
u, v, c := edge[0]-1, edge[1]-1, edge[2]
neighbors[u][v] = c
neighbors[v][u] = c
}

P := make([]int, n)
PP := make([][]int, n)
for i := 0; i < n; i++ {
PP[i] = make([]int, MAX_LEVEL)
}

begin := make([]int, n)
end := make([]int, n)
// S := make([]int, n)
var dfs func(p, u int, time *int)

dfs = func(p, u int, time *int) {
*time++
begin[u] = *time

P[u] = p
PP[u][0] = p
for level := 1; level < MAX_LEVEL; level++ {
t := PP[u][level-1]
if t > 0 {
PP[u][level] = PP[t][level-1]
}
}

for v := range neighbors[u] {
if v == p {
continue
}
dfs(u, v, time)
}
end[u] = *time
}

dfs(0, 0, new(int))

es := make(Edges, n-1)

for i := 0; i < n-1; i++ {
edge := edges[i]
u, v, c := edge[0]-1, edge[1]-1, edge[2]
if P[u] == v {
u, v = v, u
}
// u is parent of v
es[i] = Edge{u, v, c}
}

// sort by cost
sort.Sort(es)

isAncestor := func(u, v int) bool {
return begin[u] <= begin[v] && end[v] <= end[u]
}

isInPath := func(p, u, v int) bool {
return isAncestor(p, u) && isAncestor(u, v)
}

lca := func(u, v int) int {
if isAncestor(u, v) {
return u
}

if isAncestor(v, u) {
return v
}

x := u
for i := MAX_LEVEL - 1; i >= 0; i-- {
p := PP[x][i]
if !isAncestor(p, v) {
x = p
}
}

return PP[x][0]
}

res := make([]int, Q)

for i := 0; i < Q; i++ {
query := queries[i]
u, v, k := query[0]-1, query[1]-1, query[2]
p := lca(u, v)
j := sort.Search(len(es), func(j int) bool {
return es[j].c > k
})
var ans int
for a := 0; a < j; a++ {
x, y, c := es[a].p, es[a].u, es[a].c
if isInPath(p, x, u) && isInPath(p, y, u) {
// p -> x -> y -> u
ans ^= c
} else if isInPath(p, x, v) && isInPath(p, y, v) {
// p -> x -> y -> v
ans ^= c
}
// no other cases
}
res[i] = ans
}

return res
}

type Edge struct {
p, u, c int
}

type Edges []Edge

func (edges Edges) Len() int {
return len(edges)
}

func (edges Edges) Less(i, j int) bool {
return edges[i].c < edges[j].c
}

func (edges Edges) Swap(i, j int) {
edges[i], edges[j] = edges[j], edges[i]
}``````
##### Pishty and tree CodeChef Solution Review:

In our experience, we suggest you solve this Pishty and tree CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Pishty and tree CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Pishty and tree CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!