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.


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.


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


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.


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



73% Solution Ratio

Um_nikEarliest, 1M ago

gryffindoFastest, 0.8s

gryffindoLightest, 88 MB

Deshi_TouristShortest, 2724B


Login to submit


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