Dp on Trees

Revision en2, by theoneandonlytron, 2026-11-16 05:07:14

This blog is for documenting my learning journey in competitive programming. Hope someone enjoys it and finds it helpful for their own learning.

Credit to Usaco Guide and Chatgpt introduced to me a lot of great memory reducing method and a lot of fun problems:

  • Before doing Dp on Trees, i would recommend do other simple dp such as knapsack, simple dp, bitmask dp, dp digit..
  • If you know the other dp then it would be MUCH MUCH easier to understand dp on tree
  • Theory

  • Mainly Dp on tree mainly focuses on to minimise / maximise / grouping rather than counting, but counting is still pretty popular option
  • Dp on tree focuses on find optimal dp[node][some state] for a children subtree and transitioning it to the parent subtree where a leaf is a base case, this only works because the dp only flow in ONE DIRECTION, thats why dp on tree technically could be applied to a DAG.
  • There is no typical template for dp on tree but here is how it probably will looked like: void dfs(int node, int parent){ for (auto &p : adj[node]){ if (p != parent){ dfs(p, node); // transition dp } } // more transitioning. }

Problems: - https://codeforces.me/contest/1387/problem/B1 + This problem could be solved by greedy, but if anyone cannot solve it by greedy, heres my much longer dp solution :)) + How could we optimalised the minimum move, the first instinct is for a node to swap with its neighbore therefore achieving minimum, we call that a "pair-swap" + but we cannot all pair swap for like stars or intersection where anode is neighbor of like a quadrillion node, so the second shape it could be is a star, why a star, because if the length of the branch of the star exceed 2, we can perform a "pair swap" and lower the star down, now we just need to caculate the cost for a start with n children, and we get this formula: + First children : 2, Plus 2 for each additional children + this work because the first children can go to the center, center could go to some other children, and the other children that is not the first one and swap with each other, each moving distance of 2. + we can formulate this dp using the following idea: + dp[i][0] = not in any star + dp[i][1] = is a children of a star + dp[i][2] = center of a star and trace :), very pain to do dp on this problem which I did. Greedy Sol: + greedy sol is swapping each node with there parent if current state of node == orginial home, or state of parent == orginal parent home, this add 2 to the answer, why does this work? + we use the "pair-swap" idea, the stars are left, the swapping a node with the parent node could have the following result: + removing both node from their original home (of course optimal) + removing one node from their home, this idea help us get the minimum amount of the second operation which allow minimal cost.

  • https://codeforces.me/contest/1521/problem/D
  • This problem is simpler than the other one, because we can use a dp on tree approach as follow:
  • dp[i][0] = keep 0 edges
  • dp[i][1] = keep 1 edges
  • dp[i][2] = keep 2 edges and we can formula the following:
  • dp[i][0] = sum dp[children][2]
  • dp[i][1] = sort by dp[children][2] — dp[children][1], which allow us to take the one with the maximal improvement, then take children[0]
  • dp[i][1] = same idea as dp[i][1] but take 2.
  • After that trace using DSU.
  • https://atcoder.jp/contests/abc259/tasks/abc259_f

  • For me Intution just popped in and say to me, dp[i][2]
  • dp[i][0] = connect to di — 1 edges in the children
  • dp[i][1] = connect to di edges in the children.
  • the idea of sorting the same as the above problem.
  • https://usaco.org/index.php?page=viewproblem2&cpid=1019

  • The idea for this problem is to stimulate the path, why?, because for a fix k, the path length coming out of a subtree is fixed which mean we just need to stimulate and doing a pairing system using the map.
  • The second observation is if we can partition the edges to path of length k, then k must be a factor of (n-1), so we just need to traverse on each i where k % i == 0.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English theoneandonlytron 2026-11-16 06:17:57 301
en5 English theoneandonlytron 2026-11-16 06:07:47 509 (published)
en4 English theoneandonlytron 2026-11-16 06:05:02 17229
en3 English theoneandonlytron 2026-11-16 05:37:43 3699
en2 English theoneandonlytron 2026-11-16 05:07:14 3670
en1 English theoneandonlytron 2026-11-16 00:45:09 499 Initial revision (saved to drafts)