Given a tree with n nodes, rooted at 1. You have q offline queries with the form of ui, vi and xi. You have to add xi to every node in the simple path from ui to vi. It is guaranteed than ui is an ancestor of vi. Then you have to print out the values of all the nodes. The limit is... well, too large for O(n^2). Could anyone give me an approach to this problem?
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2024 16:27:51 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Since you asked for an approach, I won't go in details, but just give the approach.
Edit: Seems like I've overkilled it for both online and offline. Refer to Bedge's solution for the simple approach.
For O(log) amortized time for a query you can use centroid decomposition. Each time you find the centroid you can process all queries that pass through it in constant amortized time per query.
Additionally, in case you want to solve the problem online, there's a O(log2) per query solution using heavy-light decomposition with lazy-propagation segment trees for the heavy paths.
Thank you for your help. The term sounds very new, but i will try my best to understand it.
I didn't quite understand how to process queries on centroid tree (let's say we already built it). Can you elaborate more?
Boils down to pretty much Bedge's solution but even slightly simpler. However since that solution will work for the whole problem, doing centroid decomposition is an overkill.
I still couldn't think of a centroid decomposition approach for this problem but there is a heavy-light decomposition approach, which is pretty much straight forward like ulna's trick but for log(n) arrays.
Another approach is to use partial sum on tree.
For every query(u, v, x), add x to v and - x to parent(u).
Then run a dfs in root, add all children's value of every node.
Like:
d would be the answer array.
Thank you for your help. This sounds simpler but i will try to be able to implement both.
https://codeforces.com/contest/1076/problem/E
Similar problem if you want to try another one.