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
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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
Название |
---|
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).