Original link: https://www.shuizilong.com/house/archives/tree-divide/
The idea of tree divide and conquer is simple, but there are many changes in details and it is difficult to template (at least I am used to adding a bunch of global variables in my code… 囧). .
Specifically can be divided into. . Point divide and conquer, edge divide and conquer, and chain divide and conquer. . . (That is, various tree chain divisions, maybe it can also be classified into the category of tree division and conquer?). .
More troublesome is the dynamic tree divide and conquer. .
https://oi-wiki.org/graph/dynamic-tree-divide/
This is definitely a confusing name. . . In the end you are “dynamic tree” divide and conquer, or “dynamic” tree divide and conquer. . . (Actually, of course, the latter. But in fact, some problems solved by dynamic tree divide and conquer can indeed be solved by dynamic tree. = = … Maybe the name of the dotted tree is better?)
In addition, there is a recently learned problem of using tree divide and conquer instead of dynamic programming to find the extremum of a convex function on a class of trees. . .
https://vjudge.net/contest/122467#overview
divide and conquer
point tree
- https://vjudge.net/problem/HDU-4918
- http://hihocoder.com/problemset/problem/1065
- SRM 624 Div1 1000 TreeColoring
Finding the extremum of a convex function on a tree
This article is reprinted from: https://www.shuizilong.com/house/archives/tree-divide/
This site is for inclusion only, and the copyright belongs to the original author.