Дерево — Eolymp

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 1 0^{6})$ n\:(1 \le n \le 10^6) — кількість вузлів у дереві.

Кожен з наступних $n - 1$ n - 1 рядків містить два цілі числа $a_{i}$ a_i і $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ b_i\:(1 \le a_i, b_i \le n) — номери вершин, з'єднаних ребром.

У $i$ -му з наступних $n$ рядків записано ціле число $x_{i} (1 \leq x_{i} \leq 1 0^{9})$ x_i\:(1 \le x_i \le 10^9) — магія $i$ -ї вершини.

Вихідні дані

Виведіть магію шляху з мінімальним значенням у вигляді нескоротного дробу $P / Q (P$ P/Q\:(P і $Q$ взаємно прості числа). У всіх тестових прикладах потрібні $P$ і $Q$ менші, ніж $1 0^{18}$ 10^{18}.

Приклади

Перший тест. Зверніть увагу, що шлях може починатися і закінчуватися в одному і тому ж вузлі. Шлях з мінімальною магією складається з вузла з магією $3$ , тому магія всього шляху дорівнює $3/1$ .

Другий тест. Шлях, що складається з вершин $2$ і $4$ , є магічним $(1 \cdot 1) /2 = 1/2$ (1 \cdot 1)/2 = 1/2. Це також шлях з мінімально можливою магією.

Приклад 1

Loading

Приклад 2

Loading