GCPC11J - Time to live

As you might know, most computer networks are organized in a tree-like fashion, i.e. each computer is reachable by each other computer but only over one, unique path.

The so-called Time to live (TTL) specifies after how many hops a network packet is dropped if it has not reached its destination yet. The purpose of the TTL is to avoid situations in which a packet circulates through the network caused by errors in the routing tables.

The placement of a router that connects the network to another network is optimal when the maximal needed TTL for packets that are sent from this router to any other computer within the same network is minimal. Given a network as specified above, you should calculate the maximal needed TTL in this network if you can select the computer that should be used as router.


The first line of the input consists of the number of test cases c that follow (1 ≤ c ≤ 100). Each test case starts with a line specifying N, the number of computers in this network (1 < N ≤ 105). Computers are numbered from 0 to N-1. Then follow N-1 lines, each specifying a network connection by two numbers a and b which means that computer a is connected to computer b and vice versa, of course (0 ≤ a,b < N).


For each test case in the input, print one line containing the optimal TTL as specified above.


1 0
3 2
2 1
0 2
2 4
3 1
6 5
3 4
0 3
8 1
1 7
1 6
2 3


hide comments
ameyanator: 2018-03-27 21:52:54

Prerequisite for this question is ->http://www.spoj.com/problems/PT07Z/

aniket000: 2017-12-29 07:49:38

any code optimization tips to avoid TLE ? , pls? :(( , im calculating levels using bfs on each vertex and storing the maximum level from each vertex and finally returning the smallest level gathered.
I have solved it using tree-diameter approach, just curious on the bfs approach.

Last edit: 2017-12-29 11:20:51
vipul_0751: 2017-12-10 07:28:31

use double dfs

vanamala: 2017-12-09 13:50:51

Can someone help me, sharing their code. ?

Last edit: 2017-12-09 13:51:14
vicky_1998: 2017-10-31 14:33:51

easy one!!!!

amulyagaur: 2017-10-19 20:25:56

just find (diameter of tree)/2

mrinal_aich: 2016-06-21 18:08:18

@Kartik Satoskar: Check this test case :
0 1
1 2
2 4
4 5
2 3
Suppose you choose vertex-3, then 'l' = 2 and hence TTL would be 1. That's Incorrect!!!

Akshay Damle: 2016-04-22 00:05:01

The router has to be placed at the graph's center. Nice problem, reminded me of CodeChef April 2016 challenge - AMAEXPER problem

Kartik Satoskar: 2015-07-17 22:02:10

Can anyone tell after finding mxlen,why we have to do
if(mxlen % 2==0)

Martin Radev: 2015-05-18 10:15:11

Careful with stack overflow. You might want to use stack<T> or just select a random root of the tree.

Added by:Adrian Kuegel
Time limit:1.807s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Tobias Werth)