Travelling Alex

4.2

6 votes
Graphs, Algorithms, Depth First Search
Problem

Given a tree with N nodes and N1 undirected edges with a constant length of 1, there is a candy shop on each of the nodes. Alex is a candy lover and he wants to try candy from each of the shops. Currently he is standing on node 1 from where he starts his traveling in order to buy candies. He plans to try candies from each shop. He wonders what is the minimum distance he will need to travel in order to be able to buy candies from each shop. Help him find the answer.

Input Format :

  • The first line contains a single integer T denoting the number of test cases, then the test case follows.
  • For each case, the first line contains a single integer N, representing the number of nodes in the graph.
  • Next N1 lines follow, containing 2 integers a and b, representing that there is an edge between node a and node b.

Output Format :

For each test case, print the minimum distance Alex will need to travel in order to be able to buy candies from each shop.

Constraints :

1T10

1N105

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For the first test case:
Alex can get candies from each of the shops by travelling a minimum distance of 6 units.
He does so by travelling in the following order:

  •     1 => 2
  •     2 => 1
  •     1 => 3
  •     3 => 4
  •     4 => 3
  •     3 => 5

For the second test case:
Alex can get candies from each of the shops by travelling a minimum distance of 11 units.
He does so by travelling in the following order:

  •     1 => 5
  •     5 => 6
  •     6 => 5
  •     5 => 7
  •     7 => 8
  •     8 => 7
  •     8 => 5
  •     5 => 1
  •     1 => 2
  •     2 => 3
  •     3 => 4
Editor Image

?