Read problems statements in mandarin chinese, russian and vietnamese as well. 

Chef has teamed up with Batman and Jim Gordon to save Gotham from Joker's plan.

There are initially N police stations each having a unique id and an encryption key.
All stations are connected, using telephone lines, directly or indirectly, to Gordon's police station 
(the one with id R).
In order to provide better protection for all people in Gotham, Batman and Chef have paid for some 
new police stations and come up a smart algorithm to test the security of a particular police station. 

There are Q queries that the two of them perform on Gotham's infrastructure each being either an addition of a new police station or 
a security test, on a particular station, using a key generated by Chef.

Your task is to help our three heroes to perform all the queries succesfully and defeat Joker.

------ Input ------ 

There is only one test case in each test file.
The first line contains two numbers, N and Q, denoting  the number of police stations and 
the number of queries respectively.
The second line contains two numbers, R and key, denoting the main station's id and 
its encryption key. 
Each of the next N-1 lines contains three numbers: u, v, k which represent that there is a 
telephone line from v to u and that u's encryption key is k.
Each of the next Q lines contains a query of form:
0 v u k: A new station with id u and encryption key k is added and connected by 
a telephone line to v 
1 v k: The security test needs two encryption keys a and b such that a minimizes the value of a xor k and b that
maximizes the value of b xor k. a and b are encryption keys that correspond to some nodes that lie on the path, formed by telephone lines,
from police station v to Gordon's police station, R.
The problem requires an online solution. Each query will be encoded using the xor between its real values and the value of the last answer. Please see the note section at the end of the statement to see a piece of code that
shows how the input should be read.

------ Output ------ 

For each operation of type 1, output a single line containing the two requested values (min-value and max-value) separated by a single space.

------ Constraints ------ 

$1 ≤ N ≤ 100,000$
$1 ≤ Q ≤ 200,000$
$1 ≤ R, u_{i}, v_{i}, key, k_{i} ≤ 2^{31}− 1$
$All ids are unique (there aren't at any time two police stations with the same id).$
$Whenever you have to connect a node u to another one v, it is guaranteed that v is already connected, directly of indirectly, to R.
$
------ Subtasks ------ 

Subtask #1 (30 points):
$1 ≤ N ≤ 5000$
$1 ≤ Q ≤ 5000$

Subtask #2 (70 points):
$Original constraints$

----- Sample Input 1 ------ 
6 4

1 2

5 1 3

2 1 4

3 2 5

4 2 1

6 3 3

1 4 2

6 0 12 0

7 12 7

4 0 7
----- Sample Output 1 ------ 
0 6

2 7

0 1
----- explanation 1 ------ 

Initially, there are 6 police stations in Gotham and our heroes have 4 operations to perform
Gordon's station is the one that has id 1 and key 2.

First query:  The values on the path from 4 to 1 are 1 xor 2 = 3, 4 xor 2 = 6 and 2 xor 2 = 0. The answer is 0 6.
Second query:  The values on the path from 10 to 1 are 6 xor 1 = 7, 3 xor 1 = 2, 5 xor 1 = 4, 4 xor 1 = 5 and 2 xor 1 = 3. The answer is 2 7.
Third query:  The values on the path from 5 to 1 are 3 xor 2 = 1 and 2 xor 2 = 0. The answer is 0 1.

The decoded version of all operations is:

1 4 2    (t v k)
0 6 10 6 (t v u k)
1 10 1   (t v k)
1 5 2    (t v k)

Note

cin >> N >> Q;
cin >> R >> key;

for (i = 0; i < N - 1; i++)
{
cin >> u >> v >> k;
}

int last_{answer} = 0;

for (i = 0; i < Q; i++)
{
cin >> t;
    
// find real value of t
t ^= last_{answer};

if (t == 0)
{
cin >> v >> u >> k;
        
// find real values for u, v, and k
u ^= last_{answer};
v ^= last_{answer};
k ^= last_{answer};
}
else
{
cin >> v >> k;

// find real values for v, and k
v ^= last_{answer};
k ^= last_{answer};
        
// compute the requested values
int min_{answer} = ...
int max_{answer} = ...

// update last_{answer}
last_{answer} = min_{answer} ^ max_{answer};  
}
}

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

String algorithms

Data structures


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
(N, Q) = map(int, input().split())
g = dict()
key = dict()
(R, Rkey) = map(int, input().split())
key[R] = Rkey
for i in range(N - 1):
	(u, v, k) = map(int, input().split())
	key[u] = k
	if u not in g:
		g[u] = []
	if v not in g:
		g[v] = []
	g[u].append(v)
	g[v].append(u)

class Trie:

	def __init__(self):
		self.root = [None, None]

	def insert(self, n):
		t = Trie()
		cur = t.root = self.root[:]
		for i in range(30, -1, -1):
			bit = n >> i & 1
			cur[bit] = [None, None] if cur[bit] is None else cur[bit][:]
			cur = cur[bit]
		return t

	def xor_max_min(self, k, minmode):
		cur = self.root
		res = 0
		for i in range(30, -1, -1):
			bit = k >> i & 1
			pref = bit if minmode else not bit
			res = res << 1 | (pref if cur[pref] is not None else not pref)
			cur = cur[pref] if cur[pref] is not None else cur[not pref]
		return res
trie = dict()
trie[R] = Trie().insert(key[R])

def dfs(u, p):
	for v in g[u]:
		if v == p:
			continue
		trie[v] = trie[u].insert(key[v])
		dfs(v, u)
dfs(R, None)
answers = []
last_answer = 0
for q in range(Q):
	(t, *rest) = map(int, input().split())
	t = t ^ last_answer
	if t == 0:
		(v, u, k) = rest
		v ^= last_answer
		u ^= last_answer
		k ^= last_answer
		trie[u] = trie[v].insert(k)
	else:
		(v, k) = rest
		v ^= last_answer
		k ^= last_answer
		t = trie[v]
		min_answer = k ^ t.xor_max_min(k, minmode=True)
		max_answer = k ^ t.xor_max_min(k, minmode=False)
		answers.append(str(min_answer) + ' ' + str(max_answer))
		last_answer = min_answer ^ max_answer
print(*answers, sep='\n')