COT - Count on a tree


You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.

We will ask you to perform the following operation:

  • u v k : ask for the kth minimum weight on the path from node u to node v

 

Input

In the first line there are two integers N and M.(N,M<=100000)

In the second line there are N integers.The ith integer denotes the weight of the ith node.

In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).

In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.

Output

For each operation,print its result.

Example

Input:
8 5
8 5 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2 
Output:
2
8
9
105

hide comments
kaushik_r: 2017-06-06 14:56:41

If we list the elements in the path from node 7 to node 8 in the given example, we'll get [7, 9, 105, 3, 7] . The 3rd minimum number in the list is 7 or 9?
EDIT: Okay its 7

Last edit: 2017-06-06 15:50:58
r_ash: 2017-05-28 06:18:17

Last edit: 2017-06-03 13:42:35
californiagurl: 2017-05-23 15:24:46

I am getting WA. Is there any tricky test case? I used persistent segment tree, and even used long long.

Last edit: 2017-05-23 15:27:13
chunkitlau: 2017-02-16 09:45:18

Last edit: 2017-02-16 09:49:50
Ravi kumar: 2016-10-26 23:25:44

n & m are greater than 10^5. cost me few wa :(

vsp4: 2016-07-23 11:33:36

Very strict time limit. Had to use fast input output and then compress code :| :| due to source limit exceeding with fast input output -_-

arjundabra: 2016-07-16 12:06:34

getting seg fault in c++ 5.1 but got ac in c++ 4.3.2.Why??

xxbloodysantaxx: 2016-06-16 11:34:31

Submit in 4.3.2 , it runs faster .
Unnecessarily strict time limit..

snow_my_dream: 2016-02-23 14:20:02

I spent ONE day on it. But why I can't Accepted!!!!

secta: 2016-02-13 13:23:16

Guys who got accepted, what's your complexity? Mine is O((N+Q)logN) and it hardly passed with a lot of optimizations :)


Added by:Fotile
Date:2012-02-14
Time limit:0.129s-0.516s
Source limit:6000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Just for fun...