I tried to solve problem e in round 199 xenia and tree using heavy light decomposition but I couldn't figure out the whole idea anyone ?
I tried to solve problem e in round 199 xenia and tree using heavy light decomposition but I couldn't figure out the whole idea anyone ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
EDIT: Wrong idea. As Xellos said: every problem has a simple, clear, obviously incorrect solution :D
thnx for your reply donot u have a link for that solution ?
This problem can be solve easier with centroid decomposition.
what is that "centroid decomposition" ?
Centroid of a tree is a vertex that after deleting it, every component will have at most n/2 vertices. You can easily prove its existence. So, using this, you can use divide and conquer on trees and if your time complexity for each merge(conquer) is O(f(n)), then the total complexity would be
; Because you did it at most 
times on each vertex(every time, the size of the component a vertex u is in it would be half of the previous one).
Almost give up, but it works. Handle the segment carefully and not affect other segment values (by limit range update between chain root and chain tail of each chain) https://codeforces.me/contest/342/submission/111296661