Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Yet Another XOR Tree Problem

By shefin · Limits 3s, 1.0 GB

You are given a tree with NN nodes. A non-negative weight is assigned to each edge of the tree.

Let’s denote F(U,V)F(U, V) as the XOR\textbf{XOR} of all weights of the edges along the simple path connecting node UU and node VV. The simple path is the path that visits each node at most once. F(U,U)=0F(U, U) = 0 for all UU.

You’ll be given some queries. In each query, there will be two integers UU and VV. You have to print the maximum value of F(U,X)F(U, X), where XX is any node that lies on the simple path between node UU and node VV.

A tree is an undirected connected graph with NN nodes and exactly N1N-1 edges. It has no cycles and there exists exactly one simple path between any pair of its nodes.

The XOR\textbf{XOR} operation is the bitwise xor operation represented with “\oplus” logic symbol, which is denoted as the "^" operator in C/C++/Java/Python.

Input

The first line of the input will contain an integer TT, the number of the test cases.

In each of the test cases, the first line will contain two integers N,QN, Q, the number of nodes of the tree, and the number of queries. Each of the next (N1)(N-1) lines will contain three integers U,V,W(1U,VN;UV;0W109)U, V, W (1\leq U, V\leq N; U\neq V; 0\leq W\leq10^9) denoting there is an undirected edge of WW weight between node UU and node VV. Each of the next QQ lines will contain two integers UU and V(1U,VN)V (1\leq U, V\leq N).

It is guaranteed that the given edges form a tree.

Scoring

Subtask 1 (10 Points):
1T1001\leq T\leq100
2N,Q1002\leq N, Q\leq 100

Subtask 2 (20 Points):
1T1001\leq T\leq100
2N,Q10002\leq N, Q\leq 1000

Subtask 3 (70 Points):
1T51\leq T\leq5
2N,Q1052\leq N, Q\leq 10^5

Output

In each query, print the maximum value of F(U,X)F(U, X) in a line, where XX is any node that lies on the simple path between node UU and node VV.

Sample

InputOutput
2
3 4
2 1 17
2 3 10
3 2
3 1
1 2
1 2
4 4
3 1 11
2 3 14
2 4 19
2 2
3 3
1 1
3 4
10
27
17
17
0
0
0
29

Discussion

Statistics


75% Solution Ratio

Um_nikEarliest, 4M ago

user.794723Fastest, 0.7s

user.794723Lightest, 88 MB

Deshi_TouristShortest, 2724B

Submit

Login to submit

Editorial

Subtask 1: Any bruteforce solution should pass. Subtask 2: In each query(U,V)query(U, V)query(U,V), ...

Toph uses cookies. By continuing you agree to our Cookie Policy.