## COCI '16 Contest 1 #4 Mag

View as PDF

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 .

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 and is .

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 , the number of nodes in the tree.
Each of the following lines contains two integers, and , the labels of nodes connected with an edge.
The of the following lines contains the integer , magic of the node.

#### Output Specification

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

In all test cases, it will hold that the required and are smaller than .

#### Scoring

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

#### Sample Input 1

2
1 2
3
4

#### Sample Output 1

3/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 , so the entire path's magic is .

#### Sample Input 2

5
1 2
2 4
1 3
5 2
2
1
1
1
3

#### Sample Output 2

1/2

#### Explanation for Sample Output 2

The path that consists of nodes with labels and is of magic .

That is also the path with the minimal possible magic.

1An undirected tree is a connected graph that consists of nodes and 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.