分块被卡成暴力.
$road$
预处理出 $S$ 到每个点的距离, $T$ 到每个点的距离.
加入一条边 $(u,v)$ 后,可能产生的路径是 $S\to u\to v\to T$ 和 $S\to v\to u\to T$ ,判断一下长度是否减小即可.
$multiset$
考虑对于所有 $x$ 相同的情况,相当于每次修改一段区间,若为 $0$ ,则 $+1$ ,否则 $\times 2$ .
用两棵线段树,一棵维护答案,另一颗维护每个位置是否为 $0$ .
修改时对状态相同的连续段一起操作,每次操作最多增加 $2$ 个连续段,操作次数仍为 $O(n)$ .
如果有很多种 $x$ ,就给每个 $x$ 开两棵线段树,利用动态开点进行处理.
$tree$
考虑链的部分,可以设 $f(i,j)$ 表示根节点的标号被继承到 $i$ , $i$ 的子树还有 $j$ 条边时,最后留下根节点标号的概率.
转移时分类讨论一下删掉哪条边以及被留下的标号.
从链上拓展到树上,只需要考虑如何合并两个子树的 $dp$ 值.
其实只要再乘上两个组合数表示删边的顺序就可以了.