### PROBLEM LINK:

**Author:** Vitaliy Herasymiv

**Tester:** Tasnim Imran Sunny

**Editorialist:** Tuan Anh

### DIFFICULTY:

MEDIUM-HARD

### PREREQUISITES:

Data Structures: Trie, Dynamic Programming, Bitwise operation

### PROBLEM:

Given a tree, with each edge being assigned a non-negative weight. The weight of the path from **u** to **v** is the XOR-sum of all the edges along the path. We need to find the path with the maximal weight.

### EXPLANATION:

Before we proceed to the problem let us define the xor-sum.

XOR operation is a bitwise “Exclusive OR” operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains **0** in all positions where the corresponding bits coincide, and **1** on the rest of the positions.

For example, **3** XOR **5** = **0112** XOR **1012** = **1102** = **6**.

And as explained in the problem statement, XOR-sum of a list of numbers is the result of XOR-ing all of them. XOR-sum of (**A1** XOR **A2** XOR … XOR **A[N]**) is defined as **A1** XOR (**A2** XOR (**A3** XOR ( … XOR **A[N]**))).

Now, coming at the problem:

Using a simple dynamic programming technique, we can calculate that **S[u]** is the weight of the path from **1** to **u**. The weight of the path from **u** to **v** is **S[u]** xor **S[v]**. It’s not hard to prove this observation. Let **c** be the lowest common ancestor of **u** and **v**.

Then,

**S[u]** = **S[c]** xor **weight(c, u)**, and

**S[v]** = **S[c]** xor **weight(c, v)**

where, **weight(x, y)** is the weight of the path from **x** to **y**.

**S[u]** xor **S[v]** = **S[c]** xor **weight(c, u)** xor **S[c]** xor **weight(c, v)** = **weight(u, v)**.

After the **S** array is prepared, our problem reduces to finding two numbers in the **S** array that give the maximal xor-sum. We will use a data structure called Trie which will help use manage the numbers when we treated them as the binary strings.

*If you are not familiar with Trie, you must read about it here and try to do some simple problems at the following links
EST, PHONELST.*

The pseudo code is given below:

```
Make an empty Trie T
FOR all number v in S
Find the maximal xor-sum of v with an numbers in the T.
Update the result
Insert v into the T.
ENDFOR
```

The heart of our solution is at the third line of the pseudo code. Suppose, that we represent each number by a 20-character binary string. Let **v = a _{1}a_{2}…a_{20}** where

**a**represents the most significant bit and

_{1}**a**represents the least significant bit. To make the xor-sum

_{20}**u**xor

**v**as large as possible (

**u**is a number in the Trie), our strategy is try finding each bit of

**u**starting from the first bit to the last bit. With each

**i**bit, we check whether the

^{th}**i**bit of

^{th}**u**can be

**1 - a**or not. If it can be, then the

_{i}**i**bit of

^{th}**u**is

**1**-

**a**since this makes the

_{i}**i**bit of the xor-sum become 1. Otherwise the

^{th}**i**bit of

^{th}**u**is a

_{i}because we don’t have a better choice.

After each step, we know one more bit of **u** and that is why Trie can help us in this process. We just need to store the current node of the Trie which corresponds to the current prefix of **u**. From this node we can easily check whether the next bit of **u** can be **0** or **1** and make the decision from that. The complexity of this solutions will be O(Nlog(Maximal weight)).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

In their solutions, there is a slight modification. They insert **all** numbers in **S** into the trie first and then

find the maximal xor-sum of each **S[i]** with an numbers in the Trie. It works because **S[i] xor S[i] = 0** so inserting all the numbers in the Trie at the beginning do not affect our result.

### RELATED PROBLEMS:

Equivalent Suffix Tries (On CodeChef)

Phone List (On SPOJ)