## CCO '13 P3 - LHC

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 512M

Problem type
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
##### Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 3

For your latest top-secret experiment, you will need a large quantity of Higgs bosons. To obtain these elusive particles, you will need to build a large hadron collider, a long circular tunnel that you can use to accelerate particles and smash them into each other.

You already have access to an extensive network of tunnels, which is guaranteed to be connected and free of cyclic paths. In other words, the existing tunnels form a tree structure. This system can be represented by junctions, labelled through , connected by tunnels, each of which connects two junctions. Tunnels can be traversed in either direction (i.e., if there is a junction from to , that junction also goes from to ).

By adding exactly one tunnel to the network, you can create a cyclic path, which you will use to build your large hadron collider. You wish to form the longest possible collider in this way, where we define length as the number of tunnels in a cycle. Also, you would like to compute the number of ways to do this– that is, the number of distinct pairs of junctions such that adding a tunnel between them forms a cycle of maximum length.

For example, in the following network, we can form a collider of length by building a tunnel between junctions and , or between and :

#### Input Specification

The first line of each test case will contain (), the number of junctions. The next lines will each contain two space-separated integers and , indicating that there is a tunnel between junctions and ().

#### Output Specification

The output should consist of a single line with two space-separated integers: the length of the longest possible collider, and the number of ways to achieve that length. Note that you may need a 64-bit integer to store the answer (long long in C/C++, LongInt in Pascal).

For test cases worth of the points, you may assume that .

#### Sample Input

5
1 3
2 3
3 4
4 5

#### Output for Sample Input

4 2

• commented on April 28, 2020, 2:36 p.m.

Can someone give me hints for this problem please?

• commented on March 12, 2020, 4:28 p.m.

I think the problem should also be tagged DP since its one of the ways of doing it

• commented on March 18, 2017, 7:00 p.m.

I was wondering, if I am stuck on a CCO problem where can I find solutions or get hints? Does anyone know if there are any editorials for the CCO? Really want to learn.

• commented on March 19, 2017, 9:20 a.m.

you can always ask for help on the slack

• commented on March 19, 2017, 11:17 a.m. edited

How do I get a DMOJ email address as it is required to login?

• commented on March 19, 2017, 12:16 p.m.

The correct link would be https://slack.dmoj.ca, which will invite whatever email you specify.

• commented on Dec. 11, 2015, 1:36 p.m.

When I try to submit code for LHC it says that there are no available judges.

• commented on March 1, 2015, 6:08 p.m.

"Not that you may need a 64-bit integer to store the answer (long long in C/C++, LongInt in Pascal)."

I assume that was supposed to be "note"

• commented on March 1, 2015, 6:18 p.m.

Fixed.