Pishty and tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A little boy Pishty lives in Khust  an ancient town in Uzhlyandia with their medieval castles and smart bears.
The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom's army. Pishty also like this castle because it hides old secrets in long halls and high towers...
The castle can be described as an undirected tree with N vertices and N  1 edges. Each edge has a magic number C.
When a group of tourists visit the castle, they are interested in a path between vertices U and V. They think that an edge is interesting if its magic number is less than or equal to K. The total attractivity of the path is the xor of all interesting edges on it.
The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor's knight, he wants to know all of this information too. But he can't do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.
Given M groups of tourists, find the total attractivity of the path for each group.
Input
First line contains one integer T, denoting the number of test cases. Then T test case descriptions follow.
The first line of each testcase contains one integer N, denoting the number of vertices.
The next N  1 lines contain information about the tree. Each line contains three integers U, V and C, which denote that between vertices U and V is an edge with magical number C.
The next line contains one integer M, which denotes the number of requests.
The next M lines contain information about the requests. Each line contains three integers U, V and K.
Output
For each request output one integer in a new line  the total attractivity of the path.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, M ≤ 10^{5}
 1 ≤ U, V ≤ N
 1 ≤ C, K ≤ 10^{9}
Subtasks :
 Subtask 1 : 1 ≤ N, M ≤ 10 (10 pts)
 Subtask 2 : 1 ≤ N, M ≤ 10^{3} (20 pts)
 Subtask 3 : 1 ≤ N, M ≤ 10^{5} (70 pts)
Example
Input: 1 5 1 2 1 2 3 2 2 4 5 3 5 10 6 5 4 5 5 4 10 5 4 1 1 2 1 4 1 10 1 5 8 Output: 7 13 0 1 4 3
Author:  fekete 
Editorial  https://discuss.codechef.com/problems/PSHTTR 
Tags  datastructure, fekete, july17, medium, sorting 
Date Added:  30032017 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 