Author: Maksym Bevza Difficulty:Simple PreRequisites:none Problem StatementYou are given tree consisting $N$ nodes. Each node $i$ has value $P_{i}$ assigned to it. All values $P_{i}$ are distinct. For each node $j$ find maximal value of node in the graph if to remove nodes adjacent to $j$ and $j$. ExplanationSubtask 1 and 2$N$ is less or equal than 10000. For each node will mark all nodes which are adjacent to it as dead(not usable), will find maximum value between nonmarked nodes.
How long it works? Obviously, the complexity of first and third step is $O(N)$, how to find the complexity of the second step? Denote $D(v)$  degree of node $v$, for vertex $i$ complexity of step 2 is equal to $D(i)$, over all iterations complexity of second step is $D(1)$+$D(2)$+..+$D(N)$, what is $2*(N1)$ for trees, we see that each edge using exactly two times. Total complexity of this algorithm is $O(N*N+2*(N2)+N*N)$ = $O(N^2)$ First and third steps are slowest in the code above, how to optimize it? We can rewrite that code a bit.
Now total complexity is $O(N+2*(N2)+N*N+2*(N2))$ = $O(N^2)$, still $O(N^2)$, we can make some observations, basically we have set, where the following operations can be performed: Subtask 3Let's use some data structure, namely in our case, the data structure which can add/erase elements, and find the maximal value in the set of these elements, but does this thing in time less than $O(N)$.
Let's write code with the map in C++, the similar code can be written in Java with Map or in Python with the dictionary.
Complexity of adding/erasing of number in such data structures is $O(log N)$, summary complexity of the first steps is $O(N log N)$, the same is for third steps, Total complexity is $O(N log N + N log N + N log N + N log N)$ = $O(N log N)$ The overall time complexity of this approach is $O(N log N)$. Solution:Setter's solution can be found here Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 18 Jan '17, 03:50

I would like to share my approach :
It gave AC in 0.19 s. You can have a look on my solution here : https://www.codechef.com/viewsolution/12589162 It just requires simple prerequisite knowledge of ability to sort structures. :) answered 18 Jan '17, 16:58

@csk111165 You can take help from Hackerrank C++ domain which have specific section of STL! answered 20 Jan '17, 12:44

can this be solved using DP on Trees? answered 18 Jan '17, 17:13

Can NyOne Tell from where to excel programming in STL using CPP . I am just a beginner.Kindly Reply.. answered 20 Jan '17, 11:05

I tried to solve this problem using adjacency list and set, and I use map iterator for finding index of maximum value. here is my implementation that takes 0.52 sec to give AC. https://www.codechef.com/viewsolution/12614486 tag used: Adjacency list, set, map, iterator answered 21 Jan '17, 11:38
@priyanshu789, what logic did you applied logic.?
(27 Feb '17, 15:29)

@arjunarul Whats the approach to solve this problem using Segment Tree ? and whats the complexity? answered 25 Feb '17, 14:03

Maintain 2 max heaps 1 of all the
Pi's Other of the Pi's of V and it's
neighbours
answered 21 Feb '18, 01:55

Seeing so many people happy with their solutions passing in 0.160.19 seconds....I am feeling weird coz my brute force passed in 0.09 seconds xD. That too, unoptimized :p. Link https://www.codechef.com/viewsolution/18990772 answered 27 Jun '18, 02:11

As an interesting aside: because the network is a tree, there can only be at most three alternative capitals, one of which is of course the next most populous planet NxtPop:
answered 07 Aug '18, 04:35
