Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Pishty and tree CodeChef Solution
Problem -Pishty and tree CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Pishty and tree CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#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 chars_read = 0;
size_t buf_pos = 0;
FILE *in = stdin;
char cur = 0;
inline char get_char() {
if (buf_pos >= chars_read) {
chars_read = fread(buf, 1, BUF_SIZE, in);
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>
inline FastInput& read_integer(T& n) {
// 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) {
return read_integer(n);
}
#if !defined(_WIN32) | defined(_WIN64)
inline FastInput& operator>>(__int128& n) {
return read_integer(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;
vector<int> adj[N];
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;
int pos[N], head[N];
void dfs_hld(int u, int top) {
pos[u] = ++timer;
head[u] = top;
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;
for (; head[u] != head[v]; u = par[head[u]]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v);
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;
adj[u].push_back(v);
adj[v].push_back(u);
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 task "C"
#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 chars_read = 0;
size_t buf_pos = 0;
FILE *in = stdin;
char cur = 0;
inline char get_char() {
if (buf_pos >= chars_read) {
chars_read = fread(buf, 1, BUF_SIZE, in);
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>
inline FastInput& read_integer(T& n) {
// 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) {
return read_integer(n);
}
#if !defined(_WIN32) | defined(_WIN64)
inline FastInput& operator>>(__int128& n) {
return read_integer(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;
vector<int> adj[N];
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;
int pos[N], head[N];
void dfs_hld(int u, int top) {
pos[u] = ++timer;
head[u] = top;
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;
for (; head[u] != head[v]; u = par[head[u]]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v);
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;
adj[u].push_back(v);
adj[v].push_back(u);
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.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
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;
InputReader in = new InputReader(inputStream);
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++;
}
void pre(InputReader in) {
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();
edges.add(new Edge(a, b, c, 0));
g[a].add(new Edge(a, b, c, 0));
g[b].add(new Edge(b, a, c, 0));
}
}
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);
}
}
static class InputReader {
BufferedReader reader;
StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
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;
using System.Threading;
// (づ°ω°)づﾐe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
public class Solver
{
class Bit
{
private readonly int size;
private readonly int[] data;
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--)
{
int n = ReadInt();
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;
int w = ReadInt();
g[u].Add(Tuple.Create(v, w));
g[v].Add(Tuple.Create(u, w));
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);
int q = ReadInt();
var a = new int[q][];
for (int i = 0; i < q; i++)
{
int u = ReadInt() - 1;
int v = ReadInt() - 1;
int w = ReadInt();
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 TextReader reader;
protected static TextWriter writer;
static void Main()
{
#if DEBUG
reader = new StreamReader("..\\..\\input.txt");
//reader = new StreamReader(Console.OpenStandardInput());
writer = Console.Out;
//writer = new StreamWriter("..\\..\\output.txt");
#else
reader = new StreamReader(Console.OpenStandardInput());
writer = new StreamWriter(Console.OpenStandardOutput());
//reader = new StreamReader("input.txt");
//writer = new StreamWriter("output.txt");
#endif
try
{
new Solver().Solve();
//var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
//thread.Start();
//thread.Join();
}
catch (Exception ex)
{
#if DEBUG
Console.WriteLine(ex);
#else
throw;
#endif
}
reader.Close();
writer.Close();
}
#endregion
#region Read / Write
private static Queue<string> currentLineTokens = new Queue<string>();
private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
public static string ReadToken() { while (currentLineTokens.Count == 0)currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
public static int ReadInt() { return int.Parse(ReadToken()); }
public static long ReadLong() { return long.Parse(ReadToken()); }
public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }
public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
{
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()
readInt(scanner.Bytes(), 0, &a)
return
}
func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
scanner.Scan()
x := readInt(scanner.Bytes(), 0, &a)
readInt(scanner.Bytes(), x+1, &b)
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
x = readInt(scanner.Bytes(), x+1, &res[i])
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
tc := readNum(scanner)
for tc > 0 {
n := readNum(scanner)
edges := make([][]int, n-1)
for i := 0; i < n-1; i++ {
edges[i] = readNNums(scanner, 3)
}
Q := readNum(scanner)
queries := make([][]int, Q)
for i := 0; i < Q; i++ {
queries[i] = readNNums(scanner, 3)
}
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--
bit.Add(st[node], p.first)
bit.Add(ed[node]+1, p.first)
} 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.
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!
