×

# [closed] [help] Educational Codeforces Round 2 : E. Lomsat gelral Codeforces

 0 Can Someone help me here - Problem - http://codeforces.com/contest/600/problem/E . Spoiler [Alert] - Proceed further only if you have done this question and submitted or You have no plan to submit this question (But want to help me :P). If you want to give this question a try then open this only after trying the question. View Content asked 31 May '18, 04:39 2.2k●1●5●16 accept rate: 10%

### The question has been closed for the following reason "The question is answered, right answer was accepted" by aryanc403 18 Oct '18, 03:45

 1 You can refer this blog on dsu on trees. This problem is the one discussed in blog and provides you with various solutions. answered 31 May '18, 04:47 3.8k●23●83 accept rate: 22% 1 Thanks for blog and quick response. (31 May '18, 04:53) 1 No problem. (Although don't mind my very late response). (01 Jun '18, 14:48)
 1 Here is the link to my code : https://repl.it/@NikhilAgrawal/lomsat-gelral Basic logic is to compute the frequency of every color in the subtree of node and then find the color with maximum frequency and sum them. But the complexity will be greater than n^2 because for every node we have perform dfs(i.e. O(n) ). So, what can we do to reduce it's complexity? Every line of code seems to be normal and quite intuitive and naive at first sight. But what is special about this code??? To understand that you need to pay attention to line 20 and 21. Only these two lines contribute to reducing complexity from n^2 to n*log(n). But question is how? Notice that it's always the smaller map which gets added or merged with larger map. So, let's say there is a node A in map m. When smaller map is merged with larger map, minimum size of resulting map is 2*(size of smaller map). So, Every node at max gets added log(n) times. So the total complexity is nlog(n).* P.S : In my piece of code I have used INF and INF+1 to store the count of max color and it's sum respectively. answered 01 Jun '18, 17:42 4★kaneki13 64●5 accept rate: 16%

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,698
×655

question asked: 31 May '18, 04:39

question was seen: 328 times

last updated: 18 Oct '18, 03:45