Hi everyone!

I'm not sure that I'll be posting here very often, but I'll be mainly outlining interesting solutions to hard problems or just noting something worthwhile to think about for competitive programming.

Although I recently promoted to the Silver division in USACO, I managed to fail horribly in solving graph problems. Before I was promoted, I also saw this issue from past Codeforces contests, especially in problem C (see 1830A - Copil Copac рисует деревья).

A recent example is 1926G - Влад и проблемы в МИТ, which I couldn't manage to solve in-contest. After trying to upsolve it and looking at the main solution, I still didn't get how dynamic programming portion over the three types of water functioned. After a very long time searching up other solutions, I suddenly got inspired to do dp over whether music was played or not at a particular node.

(I feel like a noob writing all of this up) Solution

Denote a p-node as a node that represents a partying student. Define s-node and c-node similarly for sleepy and indifferent students.

Note that in the optimal configuration, each node either hears music or doesn't hear music. Now, we cannot have a p-node that hears music nor an s-node that hears music. For each c-node, we can have any state we wish.

Typically, in many graph problems (especially those involving TREES), these "state" observations inspire a dynamic programming solution, rather than a greedy one I stupidly try to look for. Let $$$dp[u][0]$$$ denote the minimal number of walls needed to construct a valid solution for the subtree containing $$$u$$$ if node $$$u$$$ doesn't hear music, and $$$dp[u][1]$$$ if node $$$u$$$ does.