A trick for some DP-Tree problems

Правка en5, от DeadlyCritic, 2020-04-17 03:41:57

Hi, Its 4AM here and i cant sleep so i brought you a nice trick and couple of problems to practice the trick.

Introduction

(Our dp change if we change root of the tree, otherwise it wont make any sens to use this trick) Lets say we want to find $$$dp_v$$$ for every vertex in a tree, this dp must be updated using the children of vertex $$$v$$$(probable the trick still works if we can update $$$dp_v$$$ from its parent), and it works in $$$O(T)$$$ to calculate it. Also this trick will be meaning full if we want to calculate $$$val_r$$$ for every $$$r$$$, $$$val_r$$$ is equal to $$$dp_r$$$ when $$$r$$$ is the root of the tree(i hope you understand what i said). Say that the dp works in $$$O(T)$$$ time, then the trick allows you to calculate $$$val_r$$$ in $$$O(T+n)$$$.

Implementation

First calculate dp for a random root $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertex $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and also $$$dp_v$$$ can be updated the same way. Now being able to move the root with distance one, we will run a dfs from $$$rat$$$, and move the root with dfs and store $$$val_v$$$, i hope the last part wasn't as bad as i think is, my poor English don't allow me to write it in words, so i'll -write it in codes :).

See the semi-code below :

Semi-code

Applications

It will be added soon including a fairly complete solution using this trick for every application, its about 4:45 AM here :). thanks for your attention.

Теги #dp, tree_dp, trick, #dfs and similar, rerooting technique, persistent structures, persistent, #data structure

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en48 Английский DeadlyCritic 2022-01-09 07:09:59 258 Tiny change: 'n\n[link](codeforces' -> 'n\n[link](https://codeforces'
en47 Английский DeadlyCritic 2020-07-06 21:41:48 231
en46 Английский DeadlyCritic 2020-05-24 09:45:09 756
en45 Английский DeadlyCritic 2020-04-19 17:30:36 139
en44 Английский DeadlyCritic 2020-04-19 00:20:52 72
en43 Английский DeadlyCritic 2020-04-19 00:12:43 80
en42 Английский DeadlyCritic 2020-04-19 00:10:39 218
en41 Английский DeadlyCritic 2020-04-19 00:04:22 56
en40 Английский DeadlyCritic 2020-04-19 00:02:14 38
en39 Английский DeadlyCritic 2020-04-19 00:00:38 10 Tiny change: 'this will calculate move the ' -> 'this will move the '
en38 Английский DeadlyCritic 2020-04-18 23:59:56 15
en37 Английский DeadlyCritic 2020-04-18 23:58:30 9
en36 Английский DeadlyCritic 2020-04-18 23:56:03 2 Tiny change: 'ry edge($v\tou$) find $' -> 'ry edge($v \to u$) find $'
en35 Английский DeadlyCritic 2020-04-18 18:32:50 66
en34 Английский DeadlyCritic 2020-04-18 18:30:04 4 Tiny change: 'ry edge($v$ \to $u$) find $' -> 'ry edge($v\tou$) find $'
en33 Английский DeadlyCritic 2020-04-18 18:29:17 1 Tiny change: '$O(log_2n) for binar' -> '$O(log_2n)$ for binar'
en32 Английский DeadlyCritic 2020-04-18 18:19:01 86
en31 Английский DeadlyCritic 2020-04-18 18:16:23 8999
en30 Английский DeadlyCritic 2020-04-18 18:00:57 99
en29 Английский DeadlyCritic 2020-04-18 17:50:12 484
en28 Английский DeadlyCritic 2020-04-18 17:42:25 688
en27 Английский DeadlyCritic 2020-04-18 17:09:46 97
en26 Английский DeadlyCritic 2020-04-18 12:25:14 136
en25 Английский DeadlyCritic 2020-04-17 23:52:30 238
en24 Английский DeadlyCritic 2020-04-17 23:37:39 77
en23 Английский DeadlyCritic 2020-04-17 23:35:38 34 Tiny change: 'e problems, the implementation will be added.\n\nThank' -> 'e problems.\n\nThank'
en22 Английский DeadlyCritic 2020-04-17 23:35:11 1642
en21 Английский DeadlyCritic 2020-04-17 19:02:21 4
en20 Английский DeadlyCritic 2020-04-17 15:27:10 13
en19 Английский DeadlyCritic 2020-04-17 14:56:11 307 Tiny change: 'nd $u$$(u != v)$ what ' -> 'nd $u$$(u \ne v)$ what '
en18 Английский DeadlyCritic 2020-04-17 14:47:28 1599
en17 Английский DeadlyCritic 2020-04-17 12:42:25 3 Tiny change: '/abc160_f)\n///i cant o' -> '/abc160_f)//i cant o'
en16 Английский DeadlyCritic 2020-04-17 12:41:50 110
en15 Английский DeadlyCritic 2020-04-17 12:39:01 18 Tiny change: 'e way.\n\n$\binom{4}{2}$\n\n*Note:' -> 'e way.\n\n*Note:'
en14 Английский DeadlyCritic 2020-04-17 12:38:07 252 Tiny change: 'e way.\n\n*Note:' -> 'e way.\n\n$\binom{4}{2}$\n\n*Note:'
en13 Английский DeadlyCritic 2020-04-17 12:27:58 284
en12 Английский DeadlyCritic 2020-04-17 12:16:32 290
en11 Английский DeadlyCritic 2020-04-17 05:05:12 147
en10 Английский DeadlyCritic 2020-04-17 05:01:51 94
en9 Английский DeadlyCritic 2020-04-17 04:46:45 66 Tiny change: 'tions\n\n[halo](https://' -> 'tions\n\n[Tree Painting](https://'
en8 Английский DeadlyCritic 2020-04-17 03:54:24 601
en7 Английский DeadlyCritic 2020-04-17 03:46:53 20 Tiny change: ' Hi,\n Its 4AM ' -> ' Hi,\n Its 4AM '
en6 Английский DeadlyCritic 2020-04-17 03:43:46 20
en5 Английский DeadlyCritic 2020-04-17 03:41:57 12 Tiny change: 'low me to right it in wor' -> 'low me to --right-- write it in wor'
en4 Английский DeadlyCritic 2020-04-17 03:11:25 35
en3 Английский DeadlyCritic 2020-04-17 03:08:14 2 Tiny change: 'rks in $O(t)$ to calc' -> 'rks in $O(T)$ to calc'
en2 Английский DeadlyCritic 2020-04-17 03:07:48 156 (published)
en1 Английский DeadlyCritic 2020-04-17 03:05:35 2061 Initial revision (saved to drafts)