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.
- 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.
- 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.
- because this is dp on tree lets think, this problem require minimum lets say if its a tree of node, can we dp on them?
- we build a graph where theres an edge from i to F[i], we can build the following casework, if we perform operation c[i]:
- connect it to some random node, so we connect to that node, and that node must connect to itself, which cost c[i] + c[j], which is not optimal because we could just connect node i to itself which cost c[i]
- connect it to itself, C[i]
- perfom operation on F[i] to connect to itself, cost C[F[i]]
- At the end there could only be 2 operation, perform op on I or F[i], so we could formulate the dp on a tree as below :
- dp[i][0] = (No operation) add minimum dp[children][1] + min(dp[children][0], dp[children][1]);
- dp[i][1] = C[i] + min(dp[children][0], dp[children][1]);
- Lets go back to the problem, the problem is a functional graph which mean that there is going to be some cycles and trees connect to some node of the cycle, so we MUST break the cycle in order to dp.
- we cna break the cycle by assuming last node in the cycle
- if the last node in the cycle is No operation, then the last node cannot support the first node in the cycle (turning it into a tree). perform tree dp on it.
- if the last node is Operation, then we just take minimum of no, yes op on the first node, and break both the last node and first node out of the cycle, creating 2 seperate tree, which allow us to do dp on tree on both of them.
https://szkopul.edu.pl/problemset/problem/r6tMTfvQFPAEfQioYMCQndQe/site/?key=statement
- This is a functional graph, which means that we can use the Bessie Function idea to do dp on it, BUT THERES A CATCH, 32 MB OF MEMORY. so thats sad, lets do some memory caculation, F[i], visited[i] (4 mb), dp[i][2], cost[i][2] (16 mb), vector <vector > adj (absolute over limit).
- So we could optimize adj using a Condensed edge array, where we keep Start, Arr (8 mb) which allow us to keep edges by storing the range [L-R] where the edges are stored in Arr.
- Then we must change the recursion to a more memory Efficient way, we can change it to indegree peeling, which means continuously processing indegree of 0, which allowed us to process from leaf up.
- After we peel the indegree, Only the cycles are left, now we just use bessie function idea and dp on the cycle.
- this solutions is really long Greedy solution:
- we can continuously take the leaf and pair it with its parent, heres why.
- lets consider u as the leaf and v as its parent, if edge (u,v) is in the optimal set S then we should take (u,v)
- if its not then there is going to be some edge going from (v, another node) which we could take alternative and take (u,v) which will keep the result the same
- therefore taking (u,v) always provide optimal answer
- we use indegree peeling and peel the trees off, now what about the cycles, if there are cycle, meaning that the optimal solution for that tree must be the root node being white, which mean we can freely take node from this cycle without worrying the optimality of the solution, in the cycle we know that No 2 black node (node getting supervision) can be adjcent, so the maximum amount of node we can color black is cycle_length / 2.
- one of the solution for this problem could be changing all nodes to 2, which mean we only need to keep values from 1 — > 2 * N in our dp.
- this is obviously a knapsack on tree problem where we do knapsack for each connection but that will be, N * 4 * N^2 or N^3 * 4
- we can take the following observation:
- when chaing



