Recently I solved the problem [ABC311Ex] Many Illumination Plans, the time complexity of the standard solution is \mathcal O(n^{1.59}X), which is very bizarre.
Can we adapt this fascinating solution to a more formalized version for general cases? I searched online for paper about it. Fortunately, there is one (link) telling us how to work on these tree knapsacks problems using automatons. It's a technique called Heavy-Light Recursive Dynamic Programming (HLRecDP).
Introduction
There's a type of tree DP problems, where we are facing difficulty of transitions of form "merging multiple subtrees", which usually needs (\max, +) or (+, \times) convolution for transition. As we all know, (\min, +) convolution for arbitrary arrays can't be done in time complexity less than \mathcal O(V^2).
However, if we design an appropriate order of DP, only adding points instead of merging subtrees, it might be possible to reduce the time complexity.
Definitions
We'll build up an automaton of transitions.
We use the notation (q,\sigma)\to (q_1,q_2,\dots ,q_d). It means that at the current node, the initial state is q, after this node has made a decision \sigma, it will transit to d son nodes q_1,q_2,\dots,q_d.
Suppose Q is the set of states, Q_{init} is the set of initial states, \Sigma is the set of decisions that can be made on each node（also known as \{\sigma\}）, \Delta means the set of possible transitions.
We use \delta(n) to represent the diversity of transitions, which means the size of the union of (q_1,q_2,\dots,q_d)(d\le n).
Let n be the number of nodes on the tree, V be the range of values. |Q_{init}|=\mathcal O(1). Now our target is to compress \delta(n) into \mathcal O(1). From now on, we assume that the merging process is a (\max,+) convolution on two arrays of length V.
Brute force
First, we'll introduce a \mathcal O(\mathrm{poly}(n)V^2) brute force solution, but using the notations of automaton, which will help us in the following optimization.
Suppose x_{u,q}(c) is: starting from node u, the initial state is q, choosing a valid subset of points in subtree u, when the total cost is c, what is the maximum profit (we use the definition of cost and profit for (\max, +) convolution).
For leaf nodes, we can just directly initialized them with complexity \mathcal O(\delta(0)\cdot V)=\mathcal O(V).
For non-leaf nodes, we need to merge up several subtrees:
Merging up two subtrees is a process of (\max,+) convolution. w_u(\sigma) means the extra profit got when we decide to use \sigma for node u.
Heavy Light Recursive Dynamic Programming
Now we only want to do adding operations.
We can think of DSU on tree, which is a common technique. We will do heavy-light decomposition: for every node, we choose the largest subtree as the heavy subtree. For a node, we will just copy the DP values of the heavy son. But there's a problem here: (\max,+) convolution has addivity but no subtractivity. This means "undo" operations seems to be invalid.
At this moment, a very amazing idea comes out: we can't "undo" right now, why not just throw away the value of light sons and recalculate them?
More specifically，we define \mathrm{DP}(u,q) means a procedure of calculating x_{u,q}. We assume that v_1 as the heavy son, while v_2,\dots ,v_d are light sons.
First of all, we recursively call \mathrm{DP}(v_1,q), and we record the DP values for every transitions.
Next, we add the light subtrees into the current status. We should first consider every transition in \Delta, and recursively call \mathrm{DP}(v_k,q). It is worth mentioning that there might be multiple valid q's', which need to be updated independently. At last, we add the contribution of node u into it.
Let's analyze the time complexity: Suppose T(n) is the complexity for tree of size n. When not applying heavy-light decomposition, T(n)\le \delta(n)(T(n_1)+T(n_2)+\dots +T(n_k))+\mathcal O(V)，where \sum n_i=n. When k=2,n_1=n_2, we achieve the maximum, T(n)\le 2\delta(n)T(\frac{n}{2})+\mathcal O(V), so T(n)=\mathcal O((2\delta(n))^{\log n}V)=\mathcal O(n^{1+\log \delta(n)}V). If \delta(n)=2, then the complexity is \mathcal O(n^2V).
When applying heavy-light decomposition, T(n)\le T(n_1)+\delta(n)(T(n_2)+\dots +T(n_k))+\mathcal O(V)，where n_1=\max n_i. Same maximum conditions k=2,n_1=n_2 as the previous case (because all the light subtrees can't exceed \frac{n}{2}), T(n)\le (\delta(n)+1)T(\frac{n}{2})+\mathcal O(V)，so T(n)=\mathcal O(n^{\log (1+\delta (n))}V). If \delta(n)=2，then the complexity is \mathcal O(n^{\log 3}V)=\mathcal O(n^{1.59}V).
If we want to compute the answer for all subtrees, then after merging up the answer for u, we'll start another recursion on every light son v_k as the root (the heavy son is already finished), and view them as the heavy son. (In essence, we are visiting every heavy son in a certain order) This will give us the same complexity.
Several Particular Cases
Independent set problem
Set of states: Q=Q_{init}=\{0,1\}, meaning can't be chosen / arbitrary.
Set of transitions: \Delta=\{(1,0)\to (1,\dots,1),(1,1)\to (0,\dots,0),(0,0)\to (1,\dots,1)\}.
Obviously \delta(n)=2 (only all 0 / all 1 two successive states), Thus we can solve it in \mathcal O(n^{1.59}V).
Partially ordered set problem (if a node is chosen, then every node in the corresponding subtree should be chosen)
Set of states: Q=Q_{init}=\{0,1\}, meaning can't be chosen / arbitrary.
Set of transitions: \Delta=\{(1,0)\to (0,\dots,0),(1,1)\to (1,\dots,1),(0,0)\to (0,\dots,0)\}.
Obviously \delta(n)=2 (only all 0 / all 1 two successive states), Thus we can solve it in \mathcal O(n^{1.59}V).
In fact, the state of all 0 doesn't need recursions. Thus, the actual time complexity is \mathcal O(n^{\log (1+1)}V)=\mathcal O(nV).
Connected component problem
Set of states: Q=Q_{init}=\{0,1,2\}, meaning can't be chosen / not yet start choosing, arbitrary / ancestor already chosen, arbitrary.
Where transitions of (1,0) had d different branches (enumerating which son is 1).
Solving directly leads to \delta(n)=n. However, we can still observe that all 0 doesn't need recursions, reducing \delta(n) to 2, complexity \mathcal O(n^{\log (1+2)}V)=\mathcal O(n^{1.59}V).