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
|
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 :')
|
|
grey_rabb1t:
2020-01-29 08:31:56
hentai
|
|
sclchuck:
2019-08-01 04:09:56
17 10
|
|
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... |
RSS