COCI '16 Contest 1 #4 Mag

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.8s
Memory limit: 256M

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

You are given an undirected1 tree with each of its nodes assigned a magic X_i.

The magic of a path2 is defined as the product of the magic of the nodes on that path divided by the number of the nodes on the path. For example, the magic of a path that consists of nodes with magic 3 and 5 is 7.5 (\frac {3 \times 5} 2).

In the given tree, find the path with the minimal magic and output the magic of that path.

Input Specification

The first line of input contains the integer N (1 \le N \le 10^6), the number of nodes in the tree.
Each of the following N - 1 lines contains two integers, A_i and B_i (1 \le A_i, B_i \le N), the labels of nodes connected with an edge.
The i^{th} of the following N lines contains the integer X_i (1 \le X_i \le 10^9), magic of the i^{th} node.

Output Specification

Output the magic of the path with minimal magic in the form of a completely reduced fraction \frac P Q (P and Q are relatively prime integers).

In all test cases, it will hold that the required P and Q are smaller than 10^{18}.


In test cases worth 3 points total, it will hold N \le 1\,000.
In test cases worth 4.5 additional points total, there will not be a node that is connected to more than 2 other nodes.

Sample Input 1

1 2

Sample Output 1


Explanation for Sample Output 1

Notice that the path may begin and end in the same node. The path with the minimal magic consists of the node with magic 3, so the entire path's magic is \frac 3 1.

Sample Input 2

1 2
2 4
1 3
5 2

Sample Output 2


Explanation for Sample Output 2

The path that consists of nodes with labels 2 and 4 is of magic \frac {1 \times 1} 2 = \frac 1 2.

That is also the path with the minimal possible magic.

1An undirected tree is a connected graph that consists of N nodes and N - 1 undirected edges.

2A path in a graph is a finite sequence of edges which connect a sequence of vertices which are all distinct from one another.


  • 2
    jimgao  commented on Feb. 3, 2017, 5:16 p.m.

    I believe it should be 10^{18} instead of 10^18.

    • 2
      d  commented on Feb. 3, 2017, 7:54 p.m.