# Yet Another XOR Tree Problem

Replay of National High S...
Limits 3s, 1.0 GB

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

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

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

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

The $\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 $T$, the number of the test cases.

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

It is guaranteed that the given edges form a tree.

Scoring

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

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

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

## Output

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

## 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


Login to submit.

### Statistics

77% Solution Ratio
Um_nikEarliest, Jun '21
user.794723Fastest, 0.7s
mumith_fahim99Lightest, 82 MB
mumith_fahim99Shortest, 2691B
Toph uses cookies. By continuing you agree to our Cookie Policy.