In the “DFS” section of the solution to Cowntagion on the USACO guide (link: Cowntagion), why does the amount of needed cows increase if the parent node is the root node, at lines 13-16? I tried the submission without those lines and cases 4, 7, and 10 became incorrect.
Well, if all the cows leave the root node (node 1), then the parent node won’t be infected, right? We need to account for this case .
The problem says
Please help him by determining the minimum possible number of days before it could be the case that at least one cow in every farm has the disease.
So, there needs to be enough sick cows at every node to send one to each adjacent node that is not its parent, and one to itself. If a node is not the parent node, this number is equal to the number of adjacent nodes (# adjacent - parent + itself = # adjacent). If the node is the parent node, then this is equal to one more than the number of adjacent nodes (# adjacent + itself = # adjacent + 1).
Alright, I get it. Thanks to both jessechoe10 and ml1234 for helping!