Hi :)
Suppose whe have a tree that each vertex has a value
we have two types of query
1 : changing value of a vertex
2 : print the minimum value in the path of u and v
Do you have answer without hld
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/20/2024 20:01:31 (i1).
Desktop version, switch to mobile version.
Supported by
Get sqrt(n) special vertices so that at maximum of sqrt(n) level ahead of it is a special vertex by using bfs from leaf. On each special vertex store minimum value from that vertex to its special ancestor in a multiset. Update by update new value for every special vertex possible as it should be only sqrt(n) special vertices at most, and you can aid finding valid special vertice to update with lca. Every query should cost sqrt(n)log(n).