Maximum XOR Path
You are given a tree of nodes, and an integer . Each node has a value . Determine the maximum XOR-sum of the values of a path with length .
Note the length of a path is defined as how many edges are on that path, not how many nodes are on it.
We define the XOR-sum of a set of integers to be , where is the length of .
The first line contains two integers and
The next line contains integers .
The next lines contain two integers and , the edges of the tree.
On one line, you are to output the maximum XOR-sum of a path with length , or if no path exists.
Subtask 1 (10%)
Subtask 2 (10%)
Subtask 3 (10%)
All vertices will have degree at most 2
Subtask 4 (70%)
No further constraints.
Note the subtasks are disjoint, and you do not have to solve previous subtasks to solve a subtask.
5 3 1 4 2 4 2 1 2 1 3 3 4 1 5