COCI 2016/2017 - Contest 1 - Mag

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 2.0s
Memory limit: 300M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bạn được cho một cây vô hướng với mỗi đỉnh của nó được gắn với một phép thuật ~X_{i}~. Chỉ số phép thuật của một đường đi trên cây được tính bằng tích các phép thuật của các đỉnh trên đường đi chia cho số đỉnh thuộc đường đi đó. Ví dụ chỉ số phép thuật của một đường đi gồm ~2~ đỉnh có phép thuật bằng ~3~ và ~5~ sẽ là ~7.5~ ~(3 \times 5 \div 2 = 7.5)~.

Cây vô hướng có những tính chất sau:

  • Một cây vô hướng là một đồ thị vô hướng liên thông bao gồm ~N~ đỉnh và ~N-1~ cạnh.
  • Đường đi trên đồ thị là danh sách các đỉnh liên tiếp, trong đó 2 đỉnh kề nhau được nối với nhau bởi cạnh đồ thị. Một đường đi trên cây có thể bắt đầu và kết thúc ở cùng một đỉnh. Ngoài ra, một đường đi cần đảm bảo không có đỉnh nào bị lặp lại.

Hãy tìm đường đi có chỉ số phép thuật nhỏ nhất và in chỉ số đó.

Input

  • Dòng đầu tiên chứa số nguyên ~N\ (1 \leq N \leq 10^6)~ là số đỉnh của cây.
  • ~N-1~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~A_i~ và ~B_i~ ~(1 \leq A_i, B_i \leq N)~ thể hiện có cạnh nối giữa hai đỉnh ~A_i~ và ~B_i~.
  • ~N~ dòng tiếp theo mỗi dòng chứa một số nguyên ~X_i~ ~(1 \leq X_i \leq 10^9)~ là phép thuật được gắn với đỉnh thứ ~i~.

Output

In ra chỉ số phép thuật nhỏ nhất tìm được dưới dạng phân số tối giản ~P/Q~ (~P~ và ~Q~ là các số nguyên tố cùng nhau).

Bộ test đảm bảo rằng ~P~ và ~Q~ luôn nhỏ hơn ~10^{18}~

Sample 1

Input
2
1 2
3
4
Output
3/1

Sample 2

Input
5
1 2
2 4
1 3
5 2
2
1
1
1
3
Output
1/2

Subtask

  • ~4~ test có ~N \le 1000~.
  • ~6~ test tiếp theo, mỗi đỉnh thuộc cây vô hướng liên kết với không quá ~2~ đỉnh khác.
  • ~10~ test còn lại không có điều kiện gì thêm.

Giải thích

  • Ví dụ 1: Con đường có chỉ số phép thuật tối thiểu gồm một đỉnh có phép thuật bằng ~3~ vì vậy kết quả in ra là ~3/1~.
  • Ví dụ 2: Con đường có chỉ số phép thuật tối thiểu cần tìm gồm đỉnh ~2~ và đỉnh ~4~, chỉ số phép thuật lúc này bằng ~1 \times 1 \div 2 = 1/2~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.