All Tracks Algorithms Graphs Depth First Search Problem

Ben and the Omnitrix
Tag(s):

LCA, Segment Trees, Trees

Problem
Editorial
Analytics

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

SAMPLE INPUT
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
SAMPLE OUTPUT
1
5
3
15
0
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIIT Allahabad

Challenge Name

Codemania 2.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?