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
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
sclchuck: 2019-08-01 04:09:56

17 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
9 8
8 10
10 12
11 12
12 13
8 14
14 15
15 16
16 17
7 8
7 6
4 6
5 7
3 5
1 3
2 3
1 17 2
17 1 2
9 13 2
13 9 2

ans :
3
3
9
9




wzw1105: 2019-05-01 08:27:06

the data u v in the input don't guarantee that u is the father of v

zhanibek_02: 2019-03-06 14:30:19

I have no idea about it, how can I solve it?

cichipi_: 2018-10-12 04:35:43

Not specifying w range is stupid :)

Last edit: 2018-10-12 13:35:56
wolf3h2h2: 2018-06-14 01:48:19

the abslute value of the weights can be > 1e9

Last edit: 2018-06-14 02:24:21
VilimL: 2018-03-24 11:59:31

Please add new languages.

thedark: 2017-08-18 10:03:49

wtf n is not <= 1e5, wasted too much time, take limit of n 111111 to be on safe side..

Last edit: 2017-08-18 10:04:18
darkghostnj: 2017-07-26 22:05:16

the weights can be negative or bigger then 10^5 and that is why most people get WA on this problem

ankit mathur: 2017-07-17 16:45:20

I found this Tc as the trickest one.
7 7
4 10 2 2 5 5 4
1 2
2 3
3 4
4 5
5 6
6 7
1 7 1
1 7 2
1 7 3
1 7 4
1 7 5
1 7 6
1 7 7
Output:
2
2
4
4
5
5
10

Also weight of nodes could be -ve also. and weight of nodes is greater than 10^5.

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

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 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD 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...