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
|
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.
|
|
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?
|
|
r_ash:
2017-05-28 06:18:17
Last edit: 2017-06-03 13:42:35 |
|
californiagurl:
2017-05-23 15:24:46
I am getting WA. Is there any tricky test case? I used persistent segment tree, and even used long long. Last edit: 2017-05-23 15:27:13 |
|
chunkitlau:
2017-02-16 09:45:18
Last edit: 2017-02-16 09:49:50 |
|
Ravi kumar:
2016-10-26 23:25:44
n & m are greater than 10^5. cost me few wa :( |
|
vsp4:
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 -_- |
|
arjundabra:
2016-07-16 12:06:34
getting seg fault in c++ 5.1 but got ac in c++ 4.3.2.Why?? |
|
xxbloodysantaxx:
2016-06-16 11:34:31
Submit in 4.3.2 , it runs faster .
|
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 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... |