GOOGOL03 - Editorial

PROBLEM STATEMENT: [Practice][1], [Contest][2]

CATEGORY: EASY-MEDIUM

PRE-REQUISITES: Depth First Search, Minimum Spanning Tree, Graph.

EXPLAINATION:
From the statement marked bold it was clear that you had to create a minimum spanning tree from the initial given graph.
Now using DFS we can calculate how many total numbers of nodes a particular node is connected to. This is done by choosing any node as a parent and then recursively calculating it.

Once this is done, to calculate the busyness for every node, we know that any particular node is connected to n-1 other nodes (directly or indirectly, because it was a connected graph). Also we know the adjacently connected nodes of a given node. Therefore, starting from any adjacent node we multiply its connectivity with the remaining number of nodes. Doing this for all the adjacent nodes will give you the final busyness for a particular node. (See the


[3] for more clarity on this concept)

**Author:** [Prayank Mathur][4]</br>
**Tester:** [Naman Taneja][5]</br>
**Editorialist:** [Prayank Mathur][6]


  [1]: http://www.codechef.com/problems/GOOGOL03
  [2]: http://www.codechef.com/GOOG2015/problems/GOOGOL03
  [3]: http://ideone.com/IJTq27
  [4]: http://www.codechef.com/users/codingstar
  [5]: http://www.codechef.com/users/na1taneja2821
  [6]: http://www.codechef.com/users/codingstar

is this problem even solvable in python or it is a C++ centric problem???
My solution is given runtime error.Now what I did was I commented everything other than taking input, still giving runtime error.I tried with fast IO also still giving runtime error.What to be done??

@vijju123 @l_returns

link:-https://www.codechef.com/viewsolution/25349164