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
sleepntsheep:
20230929 09:28:41
Is Mo's on tree really possible here, how do I get kth weight without the extra O(lgn) factor making it O(n^(3/2)lgn) ?? 

iskhakkutbilim:
20220725 12:11:52
it is just persistent segment tree or heavy light decomposition + persistent segment tree 

deltapavonis:
20220507 21:10:41
The range of weights is not specified, but I think it stays in the range of a C++ int (I got AC by storing the weights as integers) 

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 :). 

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 
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 NCSHARP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY JULIA KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Just for fun... 