| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
I just encountered a difficult problem with no solution. Can someone help me, thanks in advance.
Given a tree with N vertices. There are Q queries, the ith query is represented by K pairs (v, r), all vertices whose distance from v is not more than r will be marked. Ask how many vertices are marked per query. Limit N <= 5e4, Q <= 5e5 + N, the total K of all queries does not exceed 5e5 + N.
Auto comment: topic has been updated by sadboi2009 (previous revision, new revision, compare).
Centroid decomposition
How do you do :))
Are queries independent?
yes
Hint: Centroid decomposition. For every ancestor of node in centroid tree, count vertices with appropriate distance. Sort of like the famous problem Xenia and Tree
How do you deal with duplicate counts?