T1 HNOI2015 实验比较
给 $n$ 个有权值的物品，$m$ 条消息，消息可以是“小于”或者“等于”，一个物品只会与一个小于等于它的东西比较，求最后权值排名方案数 mod 998244353
$n \leq 500$
sol：
考场上自闭了，考出来更自闭
相等的节点缩起来，是一个森林，你要做的是给这个森林编号，要求儿子的编号小于父亲的，求方案数
然后 dp 就完事了，$f_{(x,i)}$ 表示 $x$ 为根的子树划分成 $i$ 个编号的方案数，合并两个子树实质上是合并两个编号序列搞个 $g_{(i,j,k)}$ 表示把 $i$ 个编号和 $j$ 个编号的序列合成 $k$ 个编号的序列的方案数，一起转移即可
T2 bzoj3681 Arietta
T3 bzoj3772 精神污染
给一棵树，给 $m$ 条路径，随机选两条编号不同的，求一条包含另一条的概率
$n,m \leq 100000$
sol：
考场上想的是开个 vector 记录每个左端点的右端点都是啥，然后对欧拉序建主席树，每次把当前点挂的所有右端点差分成入栈 +1，出栈 -1
然后枚举每一条路径，定位到每条路径对应的线段树，分别查 $x->lca$，$y->lca$，$lca->lca$ 的和最后 $-1$ 就可以了（因为欧拉序好像不太滋磁直接查一条不是祖孙链的路径）
这个东西常数奇大，空间还卡，满数据 1.2s 而且没啥可优化的了
后来发现数两个矩形里的点就可以了
不过调 4K 的代码还是挺爽的
一下午写了 10K，去世
原文：https://www.cnblogs.com/Kong-Ruo/p/10581343.html