無向連通圖 G 有 n 個點，n−1 條邊。點從 1 到 n 依次編号,編号為 i 的點的權值為 Wi，每條邊的長度均為 1。圖上兩點 (u,v) 的距離定義為 u 點到 v 點的最短距離。對于圖 G 上的點對 (u,v)，若它們的距離為 2，則它們之間會産生Wv×Wu 的聯合權值。
請問圖 G 上所有可産生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？
第一行包含 1 個整數 n。
接下來 n−1 行,每行包含 2 個用空格隔開的正整數 u,v，表示編号為 u 和編号為 v 的點之間有邊相連。
最後 1 行,包含 n 個正整數，每兩個正整數之間用一個空格隔開，其中第 i 個整數表示圖 G 上編号為 i 的點的權值為 Wi。
輸出共 1 行,包含 2 個整數，之間用一個空格隔開,依次為圖 G 上聯合權值的最大值和所有聯合權值之和。由于所有聯合權值之和可能很大，輸出它時要對10007取餘。
距離為 2 的有序點對有(1,3),(2,4),(3,1),(3,5),(4,2),(5,3)。其聯合權值分别為 2,15,2,20,15,20。其中最大的是 20，總和為 74。
對于30%的資料，1<n≤100；
對于60%的資料，1<n≤2000；
對于100%的資料，1<n≤200000,0<Wi≤10000。
保證一定存在可産生聯合權值的有序點對。
View Code