VM7WC '16 #5 Gold - Jayden Studies Trees

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Jayden is a little kid that likes to study trees. From the last problem, Jayden has cut down many trees. Each tree is an undirected graph where any two nodes are connected by exactly one path. Jayden would like to find the length of the longest of the paths. That means that he wants you to do it for him.

Input Specification

The first line will have N (1 \leq N \leq 10^4). The next N-1 lines will each contain two integers x and y (1 \leq x,y \leq N), denoting that an edge connects node x with node y.

Output Specification

On a single line, print the longest path between any two nodes in the tree.

Sample Input

6
1 2
1 3
2 4
2 5
5 6

Sample Output

4

Reaching the recursion limit on Python?

You can increase the amount of calls a recursive program in Python with the following code:

import sys
sys.setrecursionlimit(x)    #x will be the maximum number of calls that a recursive function can call.

If you set x to be too big, Python might run out of memory when performing the recursive calls and generate a Segmentation Fault. Try to keep x as low as possible.


Comments


  • 1
    ramjet_engine  commented on May 27, 2017, 6:27 p.m.

    The link to the wikipedia page about trees is incorrectly formatted. The closing parenthesis at the end of the URL is not part of the link, and should be.


    • -2
      Kirito  commented on May 27, 2017, 8:10 p.m.

      Fixed


  • 13
    r3mark  commented on Feb. 17, 2016, 8:21 a.m.

    This problem gives 10.0/7.0 for AC.


  • 0
    ThreeInches  commented on Feb. 8, 2016, 4:10 p.m. edit 2

    any two nodes are connected by exactly one path

    In the sample input, two nodes 1 and 4 are not connected by exactly one path. The description should probably say 'up to one path'

    edit ah. never mind.


  • 1
    YouZ  commented on Feb. 7, 2016, 9:31 p.m.

    So when it says it connects node x to node y that path goes both ways right?


    • 1
      Zander  commented on Feb. 8, 2016, 2:24 p.m.

      yup


  • 0
    Jeffmagma  commented on Feb. 7, 2016, 10:26 a.m.

    It says that the first line will have 2 integers N, but there is only 1 integer in the sample input


    • 0
      cheesecake  commented on Feb. 7, 2016, 10:59 a.m.

      Fixed, thanks for noticing.


  • 2
    d  commented on Feb. 5, 2016, 3:45 p.m.

    Is the output 4 because there is a path of length 4?

    3\implies1\implies2\implies5\implies6


    • -2
      cheesecake  commented on Feb. 5, 2016, 3:56 p.m.

      You're right, it has been fixed.