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
7
hide comments
S:
2014-10-11 13:36:06
finally AC.. |
|
Deepak Gupta:
2014-09-23 20:42:09
Fast IO
|
|
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
保证有解吗?权值范围?
|
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... |