P5405 [CTS2019] 氪金手游

小刘同学是一个喜欢氪金手游的男孩子。 他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知： - 卡池里总共有 $N$ 种卡，第 $i$ 种卡有一个权值 $W_i$，小刘同学不知道 $W_i$ 具体的值是什么。但是他通过和网友交流，他了解到 $W_i$ 服从一个分布。 - 具体地，对每个 $i$，小刘了解到三个参数 $p_{i,1},p_{i,2},p_{i,3}$，$W_i$ 将会以 $p_{i,j}$ 的概率取值为 $j$，保证 $p_{i,1}+p_{i,2}+p_{i,3}=1$。 小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 $i$ 的概率为： $$\frac{W_i}{\sum_j W_j}$$ 小刘会不停地抽卡，**直到**他手里集齐了全部 $N$ 种卡。 抽卡结束之后，服务器记录下来了小刘**第一次**得到每张卡的时间 $T_i$。游戏公司在这里设置了一个彩蛋：公司准备了 $N-1$ 个二元组 $(u_i,v_i)$，如果对任意的 $i$，成立 $T_{u_i}

无

无

#### 样例 1 解释 $W_2$ 以 $\frac 12$ 的概率取 $1$ 或者 $2$： - 如果 $W_2=1$，那么 $T_1