So today I was working on this problem on DMOJ.

First, some observations:

• We're dealing with a tree of max size 2e5
• Result is the count of some type of paths
• DP contained-subtree etc etc

Constraint analysis: Result is bounded by something on the order of 4e10, higher than the 32-bit limit.

This is where my bad CF habits kick in.

Surely, I think, the statement asks me to mod the answer by 1e9+7. (I don't bother checking; it's part of the CF speedforces risk-optimizing mentality.)

So, I find the DP, implement, etc.. Then I test; initial WA due to an issue with how DP states are propagated (parity violation isn't checked for all propagations, etc..) which I identify pretty quickly - then another WA, 80% or so into the TC.

At this point my speedforces brain thinks: "Hey, I probably forgot to mod some of the terms, and am overflowing!" I try this, no improvement.

About 15 minutes later I go back and reread the problem statement. (Why didn't I do this earlier?) Guess what? the problem doesn't ask for mod. I remove the mod statements and everything works perfectly -_-

So yes... CF encourages bad practices indeed...

tags: programming codeforces