Detailed Explanation for Problem E of Edu Round 67

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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.