HI Everyone out there,Hope this post find you in best of your spirits.Yesterday I was attempting this SPOJ Problem here.I got the idea instantly that the state of dp will be defined as dp[node][flag] where flag denotes whether ticket has to be bought for this node or not.But I am having a hard time implementing it... Can somebody please help me in its implementation.Thanks and Have a nice day.
I may try solving it later, but I found two resources that might be interesting to you:
https://github.com/dragonslayerv2/Competitive-Programming/blob/master/spoj/PT07F.cpp
https://apps.topcoder.com/forums/?module=Thread&threadID=688173&start=0&mc=2#1290229
https://github.com/gabrielsimoes/codes/blob/master/SPOJEN/pt07f.cpp
Here is my solution. I tried to comment it so it will be easier to understand. The function that builds the lists of chains is a bit confuse. Just contact me if you have any doubts.
You may want to change your post title adding the problem name on SPOJ, so that people looking for some help on this problem may find this post easier.