Detailed Explanation for Problem E of Edu Round 67

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Problem Link: https://mirror.codeforces.com/contest/1187/problem/E

I am writing this blog partly because i wanna rethink what the solution is and partly it may help someone. So we are given a graph and we need maximum points by choosing white vertices. Obvious greedy approach to this would be to take the root add points gained by it, then take the children (as this would give the maximum points greedily) and add their points to the contribution and so on. Now the problem is we can't tell which root will be giving us an optimal answer. Also according to the input size given we cant run dfs separately for each vertex. So thus we need an observation to reduce the time complexity so that we can get Accepted. Observation:

Re rooting the vertex of the graph to any of its children only changes few things and this is the main observation needed to solve this problem. Below i choose a graph :

here i will start by choosing 2 as my root. So consider how we can get the max points here. Points by root = N(all the nodes) + points by child 1 + points by child 6.

So we can use dp to get points of children and the answer becomes dp[2] = sz[2] + dp[1] + dp[6] (sz[2] = 9)

Now what all will change if we root the vertex 1 instead of 2 ?

Let's see

Firstly lets deal with the changes of vertex 2 . Its size changes and it's dp changes so dp[2] -= dp[1] (we remove the left subtree's contribution here) dp[2] -= sz[1] (remember that size also contributed in the inital answer so we need to remove it now) sz[2] -= sz[1] (remove the size finally , dont update this before updating dp[2] due to obv reasons)

Now we have successfully dealt with the changes in the vertex 2 so now we can get the answer with tree rooted at 1 by updating it's previous values as follows dp[1] += dp[2] dp[1] += sz[2] (Because now the size of 1 is no longer just 3 but 9 as its our new root so we update that too.)

This way we can check for each vertex the max points we can get and then finally choose maximum among all of them.

Hope it Helped.

If it did plz upvote :p

Comments (7)

Show archived | Write comment?

Roach00

5 years ago, # |

← Rev. 2 →

+11

Thanks! Please write more tutorial like this of some good problems

→ Reply

SleepyShashwat

Perhaps you should also write a tutorial on how to copy usernames.

CP_Sucks

5 years ago, # ^ |

I had this username from my game handle (RS6) so i used that only. Why would i copy username from a kid :p

rishabh.ranjan

Thanks for the clear explanation. The example graph really helped. Hope you are aware of the other simpler solution using distances from a root, as well.