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
Aditya Paliwal:
20141222 01:47:41
@problemsetter, the fastest solution is double your time limit. Is it genuinely possible to do this problem in your given time limit with some algorithm?


S:
20141011 13:36:06
finally AC.. 

Deepak Gupta:
20140923 20:42:09
Fast IO


yc:
20130720 08:26:39
膜拜主席。。。 

Zhouxing Shi:
20130425 04:21:54
get WA all the time. Last edit: 20130425 07:24:25 

Ankit Chaudhary:
20130226 07:48:45
what is maximum value of weight of node here? 

Damian Straszak:
20120921 14:20:23
nice problem, but setting a source limit is pointless here 

roosephu:
20120414 08:03:21
保证有解吗?权值范围?

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 CPP14CLANG CPP14 COBOL COFFEE DDMD DCLANG 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... 