Hi,

I was doing some virtuals and found this problem 581F - Zublicanes and Mumocrates

We need to color each vertex of a tree of either color 0 or color 1, such that # of leaves of color 0 equals # of leaves of color 1 (there is an even number of leaves) and we're asked to minimize the # of "bad edges". A bad edge is an edge that connects two vertexes of different colors.

For solving it I tried a dp, I first rooted the tree at a non-leaf vertex and try dp[c][u][cnt] = minimum number of bad edges that let us paint the sub tree of u such that u is colored c and there are cnt leaves of color 0. So answer to the problem will be min( dp[0][ROOT][(#leaves)/2], dp[1][ROOT][(#leaves)/2])

For each node u I calculate this dp by starting with an empty subtree and adding one child at a time, for each child v I iterate cnt over the new size of the subtree of u, and for each cnt I iterate cntv ( cntv = how many leaves is contributing v to this cnt).

Here's the code: 19434646

I got accepted with it but this kind of dps always confuses me, I don't know how to measure time complexity. To me it seems to be not very good, I would say its something like O(N^3) at least but it ran in 109 ms for N=5000. I've done other dps like this one before and I think I'm not measuring the time correctly (major reason why I tried sending this code hehe). Could someone give me a reasoning that would led to a better measure?

Thanks.

Hope I made myself clear.