Maximum XOR Path

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

You are given a tree of N nodes, and an integer K. Each node has a value v_i. Determine the maximum XOR-sum of the values of a path with length \geq K.

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 a to be a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_k, where k is the length of a.

Input Specification

The first line contains two integers N and K (1 \leq K < N \leq 10^5)

The next line contains N integers v_i\ (0 \leq v_i \leq 10^9).

The next N-1 lines contain two integers a_i and b_i (1 \leq a_i,b_i \leq N,\ a_i \neq b_i), the edges of the tree.

Output Specification

On one line, you are to output the maximum XOR-sum of a path with length \geq K, or -1 if no path exists.


Subtask 1 (10%)

N \leq 10^3

Subtask 2 (10%)

v_i \in \{0,1\}

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.

Sample Input

5 3
1 4 2 4 2
1 2
1 3
3 4
1 5

Sample Output



There are no comments at the moment.