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

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

hide comments
2016-07-23 11:33:36
Very strict time limit. Had to use fast input output and then compress code :| :| due to source limit exceeding with fast input output -_-
2016-07-16 12:06:34 arjundabra
getting seg fault in c++ 5.1 but got ac in c++ 4.3.2.Why??
2016-06-16 11:34:31 xxbloodysantaxx
Submit in 4.3.2 , it runs faster .
Unnecessarily strict time limit..
2016-02-23 14:20:02
I spent ONE day on it. But why I can't Accepted!!!!
2016-02-13 13:23:16
Guys who got accepted, what's your complexity? Mine is O((N+Q)logN) and it hardly passed with a lot of optimizations :)
2016-02-12 15:56:09
Why have I been getting a RE result? It's well done on my computer. Can anyone give me some possible reasons?
2015-09-22 08:14:33 Zhang YuanJia
don't use vector to store edges, or you will get TLE.
2015-06-09 08:34:39 Alireza Ghorbanzadeh Neghab
got accepted using only scanf() and printf().
2015-04-13 05:22:57 chenyushuo
I have got an Accepted!
2014-12-22 01:47:41 Aditya Paliwal
@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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.