Ağac — Eolymp

Giriş

Birinci sətir ağacdakı zirvələrin sayını göstərən tam ədəd $n (1 \leq n \leq 1 0^{6})$ n\:(1 \le n \le 10^6) ehtiva edir.

Növbəti $n - 1$ n - 1 sətirin hər biri iki tam ədəd $a_{i}$ a_i və $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ b_i\:(1 \le a_i, b_i \le n) ehtiva edir — kənarla birləşdirilmiş zirvələrin nömrələri.

Növbəti $n$ sətirin hər birində $i$ -ci zirvənin magiyasını göstərən tam ədəd $x_{i} (1 \leq x_{i} \leq 1 0^{9})$ x_i\:(1 \le x_i \le 10^9) yazılıb.

Çıxış

Minimal dəyərə malik yolun magiyasını sadələşdirilməmiş kəsr şəklində $P / Q (P$ P/Q\:(P və $Q$ qarşılıqlı sadə ədədlər) çıxarın. Bütün test nümunələrində tələb olunan $P$ və $Q$ $1 0^{18}$ 10^{18}-dən kiçikdir.

Nümunələr

Birinci test. Qeyd edək ki, yol eyni zirvədə başlaya və bitə bilər. Minimal magiyalı yol magiyası $3$ olan zirvədən ibarətdir, buna görə də yolun ümumi magiyası $3/1$ təşkil edir.

İkinci test. Zirvələr $2$ və $4$ -dən ibarət yol magikdir $(1 \cdot 1) /2 = 1/2$ (1 \cdot 1)/2 = 1/2. Bu da minimal mümkün magiyalı yoldur.

Nümunə 1

Loading

Nümunə 2

Loading