传奇勇士小凯

Problem Description

传说在遥远的魔法大陆有着一个村庄叫做卡卡奇里奇，这里有$n$座房屋，$n -1$条道路，保证了任意两座房屋之间都可以通过道路相互可达。这里环境优美，居民幸福地生活着。 但是有一天晚上，原本平静的村庄突然受到一不明寄生生命体的袭击，奇怪的怪物绑架了所有居民，并控制了所有房屋。凌晨时分，在外游历的勇士小凯收到了卡卡奇里奇国王的召唤来到了卡卡奇里奇，奉命消灭所有怪物，解救整个村庄。 由于有人工智能Fairy的存在，卡卡奇里奇国王能够知道小凯和每个房屋的怪物的较量中的获胜概率是多少。在一场小凯和第$i$个房屋的怪物较量中，小凯有$\frac{p_i}{15}$的概率获得胜利，成功消灭第$i$个房屋的所有怪物，同时小凯有$1- \frac{p_i}{15}$的概率失败，那么第$i$个房屋的怪物会依旧存在，只能之后再挑战。由于没有被消灭怪物会在每个晚上恢复元气，所以每一天小凯对第$i$个房屋的怪物的战斗胜率是固定的。 经过了长途跋涉之后，小凯来到了卡卡奇里奇的1号房屋开始了战斗。每一天白天，小凯都会对当前他所在的房屋的怪物发起挑战，如果成功那么他会询问卡卡奇里奇国王然后在国王的建议之下选择一个与当前房屋相邻的（有直接的道路相连的）、还存在怪物的房屋前进（但是第二天才能对该房屋的怪物进行挑战），如果不存在这样的房屋，那么喜欢摸鱼的小凯便会离开这个村庄去摸鱼。如果挑战失败，那么小凯会在这个房屋门口休息一个晚上，等到下一天继续发起挑战。 国王希望摸鱼的小凯在村庄呆的久一点，所以他想问你在他的控制之下，小凯最多期望在村庄里停留多少天？请你以最简分数的形式告诉他这个答案。

Input

第一行一个整数$T$ $(1 \leq T \leq 20)$​，表示数据组数。 对于每组数据，第一行有一个整数$n$ $(1 \leq n\leq 10^5)$，表示房屋的数量。 接下来有$n-1$行，每行两个整数$u,v$，表示村庄的一条道路，保证没有重边，没有自环。$(1 \leq u,v \leq n,u \neq v)$​ 接下来有$n$个整数，第$i$个整数$p_i$ $(1 \leq p_i \leq 15)$表示小凯打倒第$i$个村庄的怪物的概率为$\frac{p_i}{15}$。 数据保证$\sum n\leq 5 \cdot 10^5$

Output

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

Sample Input

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

Sample Output

16/1
117/4
1965/182

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）