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 N1 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 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
7
hide comments
californiagurl:
20170523 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: 20170523 15:27:13 

chunkitlau:
20170216 09:45:18
Last edit: 20170216 09:49:50 

Ravi kumar:
20161026 23:25:44
n & m are greater than 10^5. cost me few wa :( 

vsp4:
20160723 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:
20160716 12:06:34
getting seg fault in c++ 5.1 but got ac in c++ 4.3.2.Why?? 

xxbloodysantaxx:
20160616 11:34:31
Submit in 4.3.2 , it runs faster .


snow_my_dream:
20160223 14:20:02
I spent ONE day on it. But why I can't Accepted!!!! 

secta:
20160213 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 :) 

blutrex:
20160212 15:56:09
Why have I been getting a RE result? It's well done on my computer. Can anyone give me some possible reasons? 

Zhang YuanJia:
20150922 08:14:33
don't use vector to store edges, or you will get TLE. 
Added by:  Fotile 
Date:  20120214 
Time limit:  0.129s0.516s 
Source limit:  6000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Just for fun... 