All Tracks Algorithms Graphs Depth First Search Problem

Ben and the Omnitrix

LCA, Segment Trees, Trees


Earth has been attacked by Vilgax and his troops. This time Ben is not that ready as his Omnitrix has some problems in it.

Omnitrix has erased all his old alien types and now demands to scan aliens again. So Ben asks Kevin to find some aliens for him but Kevin wants something in return. He wants Ben to solve a programming question which he was trying for months but couldn't be able to solve it.

Kevin has a tree with N nodes and some specific value on nodes. You have to answer Q queries. In each query you are given two nodes U, V and two other integers K and P. Ben take all the values of vertices in a list that come in between shortest path U-V. Then he chooses K minimum values from the list if the list has at least K elements otherwise he just takes the whole list. You have to find the Xor-sum of the chosen elements and P i.e. first take the xor and then take summation.

\(Input :\)

The first line of the input contains two integers N and Q denoting the number of nodes and number of queries. Next n-1 lines contain two nodes that have an edge between them. The next line contains n space-separated integers where ith integer denotes the value on the ith node. Next, Q lines contain 4 integers as written above.

\(Output :\)

print a single integer denoting the answer.

\(Constraints\) :

1<= N ,Q <= 10^5

1<= value on nodes,P <= 10^9

1<= K <= 20

5 5
1 3
1 2
1 4
4 5
1 2 3 4 5
4 5 6 4
1 5 2 5 
5 5 10 6
2 3 3 7
5 3 1 1

In the first query L=2 as the path between 4 and 5 contains 2 nodes. so 4(xor)4+4(xor)5 = 1.

Time Limit: 0.6 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications