AT_kupc2024_o Ordinary Blossom Algorithm

$ 1 $ から $ N $ までの番号がついた、頂点 $ 1 $ を根とする $ N $ 頂点の根付き木があります。 $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ辺です。 各頂点には重みが付いており、頂点 $ v $ の重みは $ W_v $ です。 あなたの目標は次の操作を任意の回数行い、最終的に $ 1 $ 頂点からなる木にすることです。 - 根から伸びるパスを $ 1 $ つ選び、含まれる辺を全て縮約して新しい根とする。そして、新しい根の重みをパスに含まれていた頂点の重みの総和 $ S $ に設定し、コストに $ S $ を加算する。 目標を達成する操作列で操作回数が最小となるもののうち、かかるコストの最小値と最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ W_1 $ $ W_2 $ $ \cdots $ $ W_N $

目標を達成する操作列で操作回数が最小となるものの中で、かかるコストの最小値と最大値を $ C_{\min},C_{\max} $ とする。 $ 2 $ つの値をこの順番に空白区切りで出力せよ。 > $ C_{\min} $ $ C_{\max} $

### Sample Explanation 1 $ 1 $ 頂点の木にするための最小の操作回数は $ 2 $ 回です。 最初にパス $ 1-2-4 $ を選ぶと、新しい根（頂点 $ 5 $ とする）と頂点 $ 3 $ がつながった状態になり、 $ S=50 $ が根の重みになります。次に、パス $ 5-3 $ を選ぶと木が重み $ S=51 $ の $ 1 $ 頂点となり操作が終了します。このときのコストは $ 50+51=101 $ となり、 $ 2 $ 回で目標を達成するときのコストの最大値をとります。 また、パス $ 1-3 $ （新しい根を頂点 $ 5 $ とする）、パス $ 5-2-4 $ の順に操作するとコストは $ 21+51=72 $ となり、 $ 2 $ 回で目標を達成するときのコストの最小値をとります。 ### Constraints - 入力は全て整数 - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le A_i,B_i \le N $ - $ 1 \le W_v \le 10^8 $ - 入力で与えられるグラフは木