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
princemishra:
20211202 16:12:54
really nice one 

deepkamal:
20210612 11:09:04
Can be done without persistent segment tree as well. Use mo's algorithm on trees with complexity O(n * root(n)). Though my solution passed barely after removing #define int int64_t, this never happened before, time limit was extremely close in my case :). 

treenipples:
20210416 10:52:32
Last edit: 20210602 05:53:13 

Neal Wu:
20210211 04:27:40
Why is the source code limit for this problem so small (6 KB)? I can't even submit. 

mhasan01:
20200714 04:47:11
Finally got Accepted :')


grey_rabb1t:
20200129 08:31:56
hentai


sclchuck:
20190801 04:09:56
17 10


wzw1105:
20190501 08:27:06
the data u v in the input don't guarantee that u is the father of v 

zhanibek_02:
20190306 14:30:19
I have no idea about it, how can I solve it? 

cichipi_:
20181012 04:35:43
Not specifying w range is stupid :) Last edit: 20181012 13:35:56 
Added by:  Fotile 
Date:  20120214 
Time limit:  1s 
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... 