题目描述

$Rikka$展开了一场大冒险，他来到了一座村庄，这里有$n$座房屋，$n−1$条道路， 邪恶的巫师$Flysky$要阻挠$Rikka$离开村庄， 于是他在每个房屋中都放了一个怪物， 在一场$Rikka$和第$i$个房屋的怪物较量中，$Rikka$有的 $p_i / 15$ 概率获得胜利，成功消灭第i个房屋的所有怪物，同时$Rikka$有 $1 − p_i/15$的概率失败，那么第i个房屋的怪物会依旧存在，只能之后再挑战。每一天$Rikka$对第 $i$ 个房屋的怪物的战斗胜率是固定的， 在挑战成功或失败后，$Rikka$都只能在第二天才能再次挑战 。
现在， $Rikka$位于一号房屋并开始挑战， $Rikka$不能挑战没有怪物的房屋， 巫师$Flysky$会给予$Rikka$虚假的指引， 并引导他去挑战与当前房屋相邻的且还存在怪物的房屋前进。
现在巫师$Flysky$想知道$Rikka$最多期望在村庄里停留多少天， 要求以最简分数表示。

输入格式

第一行一个整数$T (1≤T≤20)$;，表示数据组数。
对于每组数据，第一行有一个整数$n ( 1 ≤ n ≤ 10^5)$，表示房屋的数量。
接下来有$n−1$行，每行两个整数 $u, v$，表示村庄的一条道路，保证没有重边，没有自环。$(1 ≤ u, v ≤ n, u ≠ v)$;
接下来有 $n$个整数，第 i 个整数$p_i (1 ≤ p_i ≤15)$表示$Rikka$打倒第i个村庄的怪物的概率为$p_i/15$。
数据保证$∑n ≤ 5*10^5$

输出格式

对于每组数据，输出一个最简分数（$A/B$，$A$与$B$互质）表示$Rikka$最多期望在村庄里停留多少天。数据保证答案不会为$0$。

样例

3
4
1 2
2 3
1 4
15 3 5 1
5
1 2
2 3
3 4
3 5
1 5 4 2 10
5
1 2
1 3
3 4
3 5
13 14 7 12 2

16/1
117/4
1965/182