AC代码

https://codeforces.com/contest/1770/submission/188152394

题意：

Imi有一个具有n个顶点的无向树，其中边的编号从1到n−1。第i条边连接顶点ui和vi。

树上还有k只蝴蝶。最初，第i个蝴蝶位于顶点ai上。 

Koxia玩的游戏如下：

1. 对于i=1,2，…，n−1，Koxia将第i条边的方向设置为ui→vi或vi→ui的概率相等。

2. 对于i=1,2，…，n−1，如果一只蝴蝶在第i条边的初始顶点上，而末端顶点上没有蝴蝶，

那么这只蝴蝶会飞到末端顶点。注意，操作顺序为1,2，…，n−1，而不是同时进行。

3. Koxia从所有可能的k(k−1)/2种方式中以相等的概率从k只蝴蝶中选择两只蝴蝶来选择两只蝴蝶，

然后她将两个选择的顶点之间的距离作为她的分数。

现在，Koxia希望你找到她的分数的期望值，模998244353。

题解：

 组合数学 + 图论 + 概率论