Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sayadpur City

By Wiz_Khalipha · Limits 1s, 512 MB

Bob wants to visit a new country called sayadpur. There are N cities(1, 2, 3….., N) in sayadpur, and they are connected by n-1 undirected roads. You can go from one city to any other city using these roads. Each city except city 1 is directly connected with at most two cities. Bob wants to start his journey from a city and then move to any adjacent city. In his journey, he does not want to visit a city twice. For visiting a city he has to pay a cost. Suppose he visits total “k” cities and the cost of those cities are a1,a2,.aka_1,a_2,…. a_k .
The overall cost will be the
bitwise “or” of those costs (a1a2a3.aka_1 | a_2 |a_3 |…. | a_k). You have to find the maximum overall cost.

Input

First-line there is a number NN ( 1N1051 ≤ N ≤ 10^5 ).
Each of the next N-1 lines contains two integers u and v (1 ≤ u,v ≤ n, u≠v), denoting an edge connecting vertex u and vertex v.
Next line contains N integers a1,a2,..aNa_1,a_2,.. a_N. The first element is the cost of city number 1, the second element is the cost of city number 2 city and so on.
(1 ≤ aia_i ≤ 2047, 1 ≤ i ≤ N)

Output

Output one integer, the maximum overall cost.

Sample

InputOutput
3
1 2
1 3
1 2 4
7

Discussion

Statistics


69% Solution Ratio

YouKnowWhoEarliest, Aug '20

user.953511Fastest, 0.0s

helium_00Lightest, 6.5 MB

zishan044Shortest, 626B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.