唐氏模拟赛，这没 AK 我是不是该退役了

A

枚举矩形上下边界所在的行，拿个桶扫一遍容易算出这两行的贡献。

B

【模板】离散化 + 【模板】差分

C

区间 DP，\(f_{i,j}\) 表示只留 \(i\) 子树，所有询问用到的区间个数之和最小是多少。

D

计数转概率。

如果是树的话，考虑维护 \(p_i\) 表示当前 \(i\) 上有猫的概率，狗跑到 \(i\) 点时令 \(p_i'\gets p_i\times p_j,p_j'\gets p_j+p_i(1-p_j)\)。

但是这是基环树，连接环上最后一条边 \(u,v\) 时，\(p_u\) 和 \(p_v\) 并不独立，然后就炸了。

考虑连接环上最小的点 \(o\) 与其父亲 \(f_o\) 时，钦定它们上面有没有猫，这样连接环上最后一条边时 \(p_u\) 和 \(p_v\) 就独立了。

冷知识：“薛定谔的猫”实验在巴普洛夫死前一年提出。