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
sleepntsheep: 2023-09-29 09:28:41

Is Mo's on tree really possible here, how do I get k-th weight without the extra O(lgn) factor making it O(n^(3/2)lgn) ??

iskhakkutbilim: 2022-07-25 12:11:52

it is just persistent segment tree or heavy light decomposition + persistent segment tree

deltapavonis: 2022-05-07 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: 2021-12-02 16:12:54

really nice one

deepkamal: 2021-06-12 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: 2021-02-11 04:27:40

Why is the source code limit for this problem so small (6 KB)? I can't even submit.

mhasan01: 2020-07-14 04:47:11

Finally got Accepted :')
Few notes here:
1. Use Fast I/O - getchar and putchar
2. Don't use vector
3. Use persistent segment tree
4. Use g++ (4.3.2) (I need to change some few codes because of this)

Conclusion: Time Limit too dang strict :(

grey_rabb1t: 2020-01-29 08:31:56

hentai

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


Added by:Fotile
Date:2012-02-14
Time limit:1s
Source limit:6000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Just for fun...