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
chenyushuo: 2015-04-13 05:22:57

I have got an Accepted!

Aditya Paliwal: 2014-12-22 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?

re(vamsi): time limit is for a single test file. time taken by a solution is time elapsed for all test files

Last edit: 2015-02-19 14:57:30
S: 2014-10-11 13:36:06

finally AC..

Deepak Gupta: 2014-09-23 20:42:09

Fast IO
getchar->TLE
getchar_unlocked->AC

yc: 2013-07-20 08:26:39

膜拜主席。。。

Zhouxing Shi: 2013-04-25 04:21:54

get WA all the time.

Last edit: 2013-04-25 07:24:25
Ankit Chaudhary: 2013-02-26 07:48:45

what is maximum value of weight of node here?

Damian Straszak: 2012-09-21 14:20:23

nice problem, but setting a source limit is pointless here

roosephu: 2012-04-14 08:03:21

保证有解吗?权值范围?
P.S. “perfrom” -> "perform "
保证。。longint内

Last edit: 2012-04-23 05:31:21

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