fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long 
  5.  
  6. vector<vector<int> > graph;
  7. vector<int> str;
  8. vector<int> emd;
  9. vector<pair<pair<int,int>,int> > edges;
  10.  
  11. vector<int> q1;
  12. vector<int> q2;
  13.  
  14. int timer;
  15.  
  16. void dfs(int node,int parent){
  17. 	str[node]=timer;
  18.  
  19. 	int len = graph[node].size();
  20. 	for (int i=0;i<len;i++){
  21. 		int node1 = graph[node][i];
  22. 		if (node1!=parent){
  23. 			timer+=1;
  24. 			dfs(node1,node);
  25. 		}
  26. 	}
  27. 	emd[node]=timer;
  28. }
  29.  
  30. vector<int> sgtree;
  31.  
  32. void update(int node,int start,int end,int idx,int value){
  33. 	if (start==end){
  34. 		sgtree[node] ^= value;
  35. 		//cout<<sgtree<<endl;
  36. 		return;
  37. 	}
  38. 	else{
  39. 		int mid = (start+end)>>1;
  40. 		if (start<=idx && idx<=mid){
  41. 			update(2*node,start,mid,idx,value);
  42. 		}
  43. 		else{
  44. 			update(2*node+1,mid+1,end,idx,value);
  45. 		}
  46. 		sgtree[node] = sgtree[2*node]^sgtree[2*node+1];
  47. 		//cout<<sgtree<<endl;
  48. 	}
  49. }
  50.  
  51. int query(int node,int start,int end,int l,int r){
  52. 	if (r<start | end<l){
  53. 		return 0;
  54. 	}
  55. 	if (l<=start && end<=r){
  56. 		return sgtree[node];
  57. 	}
  58. 	int mid = (start+end)>>1;
  59. 	int p1 = query(2*node,start,mid,l,r);
  60. 	int p2 = query(2*node+1,mid+1,end,l,r);
  61. 	return (p1^p2);
  62. }
  63.  
  64.  
  65. int main(){
  66. 	int test;
  67. 	cin>>test;
  68. 	while(test--){
  69. 		int n,m;
  70. 		cin>>n;
  71. 		graph.clear();
  72. 		graph.resize(n+1);
  73.  
  74. 		str.clear();
  75. 		str.resize(n+1);
  76. 		emd.clear();
  77. 		emd.resize(n+1);
  78. 		edges.clear();
  79. 		//edges.resize(n+1);
  80.  
  81.  
  82. 		timer=0;
  83.  
  84. 		for (int i=1;i<n;i++){
  85. 			int u,v,w;
  86. 			cin>>u>>v>>w;
  87. 			edges.push_back(make_pair(make_pair(u,v),w));
  88.  
  89. 			graph[u].push_back(v);
  90. 			graph[v].push_back(u);
  91. 		}
  92. 		dfs(1,-1);
  93.  
  94. 		vector<pair<int,int> > sorted;
  95.  
  96. 		for (int i=0;i<n-1;i++){
  97. 			if (str[edges[i].first.first]<str[edges[i].first.second]){
  98. 				swap(edges[i].first.first,edges[i].first.second);
  99. 			}
  100. 			sorted.push_back(make_pair(edges[i].second, -edges[i].first.first));
  101. 		}		
  102. 		cin>>m;
  103. 		q1.clear();
  104. 		q1.resize(m);
  105. 		q2.clear();
  106. 		q2.resize(m);
  107.  
  108. 		vector<int>ans(m,0);
  109.  
  110. 		for (int i=0;i<m;i++){			
  111. 			int u,v,c;
  112. 			cin>>u>>v>>c;
  113. 			q1[i]=u;
  114. 			q2[i]=v;
  115. 			sorted.push_back(make_pair(c,i));
  116. 		}
  117. 		sort(sorted.begin(),sorted.end());
  118.  
  119. 		sgtree.clear();
  120. 		sgtree.resize(400005,0);
  121.  
  122. 		int len = sorted.size();
  123. 		for (int i=0;i<len;i++){
  124. 			if (sorted[i].second<0){
  125. 				int node = -sorted[i].second;
  126. 				int value = sorted[i].first;
  127.  
  128. 				// use of segment tree is required here
  129. 				update(1,0,n-1,str[node],value);
  130. 				update(1,0,n-1,emd[node]+1,value);
  131. 			}
  132. 			else{
  133. 				//
  134. 				int idx = sorted[i].second;
  135. 				ans[idx] = query(1,0,n-1,0,str[q1[idx]])^query(1,0,n-1,0,str[q2[idx]]); 
  136. 			}
  137. 		}
  138.  
  139. 		for (int i=0;i<m;i++){
  140. 			cout<<ans[i]<<endl;
  141. 		}	
  142. 	}
  143. 	return 0;
  144. }
Runtime error #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5lRSww
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!