| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
classical problem: add delta to all nodes on the path to u->v, it is basically adding delta to u and v, then val[lca(u,v)]-=delta, then just use dfs to find answer.
My question is to ask: is there a way to answer online?
Like let us say we have q<=1e5 queries and n<=1e5: is there a way to find value of a node during queries? (just curious)
You can use HLD (Heavy Light Decomposition).
Actually, you can use the similar approach to the one you have mentioned to get an online solution. When a query "add $$$d$$$ to all vertexes on path from $$$u$$$ to $$$v$$$" comes, increase values of $$$u$$$ and $$$v$$$ by $$$d$$$ and decrease values of $$$LCA(u, v)$$$ and $$$ancestor(LCA(u, v))$$$ by $$$d$$$. In order to answer a query "get value of vertex $$$u$$$" we need to take a sum over it's subtree.
To efficiently get sums over subtrees and modify values in particular vertexes we can use the following construction. Let's traverse our tree using DFS. Notice, that all vertexes from a subtree of any vertex $$$u$$$ form a segment in the traversing. So to get a sum over a subtree of vertex $$$u$$$, we can just get a sum over a segment of the traversing from $$$tin[u]$$$ to $$$tout[u]$$$. Finally, to get sums over segments and modify elements in $$$O(log(n))$$$ we can use segment tree.
This way the solution will work with $$$O(q \cdot log(n))$$$ time and $$$O(n)$$$ or $$$O(n \cdot log(n))$$$ memory depending on the LCA implementation.
Actually, I didn't know about this approach, thank you for sharing!
oh, so instead you do it like flattening then do segtree. thanks for the answer
what's online and offline query
online query means reading query one by one and processing them individually. offline query means reading all the query and processing them may be in reverse order or sorted order or some others way
use link-cut-tree, it is $$$O((n+q)\log n)$$$
use heavy light decomposition O(q * log^2n) complexity