fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair <int, int>
  4. #define mp make_pair
  5. #define F first
  6. #define S second
  7. #define ll long long
  8. #define iosbase ios_base::sync_with_stdio(false)
  9. #define sc scanf
  10. #define pr printf
  11. #define null NULL
  12. #define getcx getchar_unlocked
  13. #define lb lower_bound
  14. #define ub upper_bound
  15. #define all(x) x.begin(), x.end()
  16. #define pll pair<ll,ll>
  17. #define vi vector <int>
  18. #define vll vector <ll>
  19.  
  20. #define maxs 200005
  21. #define logmaxs 35
  22.  
  23. #define MOD 1000000007
  24. #define eps 1e-9
  25. #define llmax 1e15+5
  26. #define intmax 1e9+5
  27. #define intmin -intmax
  28.  
  29. #define pi 3.14159265358979
  30.  
  31. using namespace std;
  32.  
  33. int x[maxs], y[maxs], z[maxs];
  34. vector <pii> gr[maxs];
  35. int vis[maxs];
  36. int xr[maxs];
  37. int dpth[maxs];
  38. int cnt;
  39. int l[maxs], r[maxs];
  40.  
  41. void dfs(int src, int p){
  42. 	vis[src]=1;
  43. 	cnt++;
  44. 	xr[cnt]=p;
  45. 	l[src]=cnt;
  46. 	for(int i=0; i<gr[src].size(); i++){
  47. 		if(!vis[gr[src][i].F]){
  48. 			dpth[gr[src][i].F]=dpth[src]+1;
  49. 			dfs(gr[src][i].F, p^gr[src][i].S);
  50. 		}
  51. 	}
  52. 	r[src]=cnt;
  53. }
  54.  
  55. int tree[4*maxs], lazy[4*maxs];
  56.  
  57. int getmid(int a, int b){
  58. 	return (a+b)/2;
  59. }
  60.  
  61. int merge(int a, int b){
  62. 	return a^b;
  63. }
  64.  
  65. void init(int a, int b, int idx){
  66. 	if(a>b){
  67. 		return ;
  68. 	}
  69. 	if(a==b){
  70. 		tree[idx]=xr[a];
  71. 		//cout<<xr[a]<<" "<<a<<endl;
  72. 		return ;
  73. 	}
  74. 	int mid=getmid(a, b);
  75. 	init(a, mid, 2*idx);
  76. 	init(mid+1, b, 2*idx+1);
  77. 	tree[idx]=merge(tree[2*idx], tree[2*idx+1]);
  78. }
  79.  
  80. void update(int node,int a,int b,int i,int j,int val){
  81. 	if(lazy[node]!=0){
  82. 		tree[node]^=lazy[node];
  83. 		if(a!=b){
  84. 			lazy[node*2]^=lazy[node];
  85. 			lazy[node*2+1]^=lazy[node];
  86. 		}
  87. 		lazy[node]=0;
  88. 	}
  89. 	if(a>b || a>j || b<i){
  90. 		return ;
  91. 	}
  92. 	if(a>=i && b<=j){
  93. 		tree[node]^=val;
  94. 		if(a!=b){
  95. 			lazy[node*2]^=val;
  96. 			lazy[node*2+1]^=val;
  97. 		}
  98. 		return ;
  99. 	}
  100. 	update(node*2,a,(a+b)/2,i,j,val);
  101. 	update(node*2+1,(a+b)/2+1,b,i,j,val);
  102. 	tree[node]=tree[node*2]^tree[node*2+1];
  103. }
  104.  
  105. int query(int node,int a,int b,int i,int j){
  106. 	if(a>b || a>j || b<i){
  107. 		return 0;
  108. 	}
  109. 	if(lazy[node]!=0){
  110. 		tree[node]^=lazy[node];
  111. 		if(a!=b){
  112. 			lazy[node*2]^=lazy[node];
  113. 			lazy[node*2+1]^=lazy[node];
  114. 		}
  115. 		lazy[node]=0;
  116. 	}
  117. 	if(a>=i && b<=j){
  118. 		return tree[node];
  119. 	}
  120. 	int q1=query(node*2,a,(a+b)/2,i,j);
  121. 	int q2=query(node*2+1,(a+b)/2+1,b,i,j);
  122. 	return (q1^q2);
  123. }
  124. int main(){
  125. 	int n;
  126. 	sc("%d", &n);
  127. 	for(int i=1; i<=n-1; i++){
  128. 		sc("%d %d %d", &x[i], &y[i], &z[i]);
  129. 		gr[x[i]].pb(mp(y[i],z[i]));
  130. 		gr[y[i]].pb(mp(x[i],z[i]));
  131. 	}
  132. 	dfs(1, 0);
  133. 	init(1, n, 1);
  134. 	int q;
  135. 	sc("%d", &q);
  136. 	int t;
  137. 	int x1,y1;
  138. 	while(q--){
  139. 		sc("%d %d %d", &t, &x1, &y1);
  140. 		if(t==1){
  141. 			int zz;
  142. 			int u1=x[x1];
  143. 			int u2=y[x1];
  144. 			if(dpth[u1]<dpth[u2])
  145. 				zz=u2;
  146. 			else zz=u1;
  147. 			update(1, 1, n, l[zz], r[zz], y1^z[x1]);
  148. 			z[x1]=y1;
  149. 		}
  150. 		else{
  151. 			pr("%d\n", query(1, 1, n, l[x1], l[x1])^query(1, 1, n, l[y1], l[y1]));
  152. 		}
  153. 	}
  154. 	return 0;
  155. }
Runtime error #stdin #stdout 0.06s 22416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uuLdWu
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!