JOIN
Get Time

   Problem Statement  

 Problem Statement for TwoDogsOnATree

Problem Statement

    

LYC and owaski are pet dogs of Zhangzj. They like playing on a tree.

The tree has N vertices, indexed from 0 to (N - 1). On each edge of the tree, there is a number between 0 and 1,023, inclusive. LYC will choose a path on the tree, calculate the bitwise xor of the numbers on the edges of the path. (The bitwise xor of zero numbers is 0. This applies if the path has no edges.) Then, LYC will erase all edges of the path. This will divide the tree into several connected components, each of which will be a tree again.

Once LYC is done, Owaski will choose one of those components. Then, he will choose a path in that component and calculate the bitwise xor of the numbers on its edges.

Finally, the two dogs will share the values they computed with each other, and together they will compute one final number F: the bitwise xor of their two numbers. Their goal is to work together to maximize the value of F. You are given int[]s parent and w of (N - 1) elements. For each valid i, there is an edge connecting the (i + 1)-th vertex and the parent[i], and the number on the edge is w[i].

Compute and return the largest possible value of the final number F.

 

Definition

    
Class:TwoDogsOnATree
Method:maximalXorSum
Parameters:int[], int[]
Returns:int
Method signature:int maximalXorSum(int[] parent, int[] w)
(be sure your method is public)
    
 

Constraints

-

N will be between 1 and 1,000, inclusive.

-

Both parent and w will contain exactly (N - 1) elements.

-

For each valid i, parent[i] will be between 0 and i, inclusive.

-

For each valid i, w[i] will be between 0 and 1,023, inclusive.

 

Examples

0)
    
{0, 0, 0, 0}
{1, 2, 4, 8}
Returns: 15

The tree contains 5 vertices and 4 edges. LYC can choose the path 1 &rarr 0 &rarr 2, and Owaski can choose the path 3 &rarr 0 &rarr 4. LYC's number will be 1 xor 2 = 3. Owaski's number will be 4 xor 8 = 12. The answer will be 3 xor 12 = 15.

1)
    
{0, 1, 2, 3, 4, 5, 6, 7, 8}
{3, 2, 6, 5, 8, 1, 3, 4, 3}
Returns: 15

The tree forms a chain of 10 vertices and 9 edges. LYC can choose the whole chain, and Owaski can choose a path containing a single vertex. The number LYC gets will be 15, and because Owaski's path contains no edges, the number will be 0. Therefore the answer will be 15 xor 0 = 15.

2)
    
{0, 0, 2, 2, 4, 4, 5, 6}
{13, 16, 12, 11, 3, 1, 4, 2}
Returns: 31

LYC can choose the path 4 &rarr 6 &rarr 8, and Owaski can choose the path 0 &rarr 2 &rarr 3.

3)
    
{0, 0, 2, 0, 1, 2, 2, 4, 6, 1, 5}
{628, 589, 815, 864, 459, 507, 733, 239, 904, 592, 818}
Returns: 1017
4)
    
{}
{}
Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 719 Round 1 - Division II, Level Three