【题解】Luogu“Cai 的一场公开赛”

首先看看选手的表现 :

由于是 oj 上的比赛，所以我就不写暴力的做法了

A change

首先你需要知道你要求的答案是图上最小生成树的边权之和再加一

你还要知道这张图是需要加边和删边的

可持久化 LCT

动态最小生成树应该都会写，如果不会的可以先去做 NOI 的魔法森林

其实可以线段树分治，Luogu 举办了这么多比赛，应该有考过

线段树分治就是说你把所有的边，按照它存在的时间丢到线段树上面，这样一条边就最多会被丢到线段树的 log 个区间上，这样你就发现 LCT 只需要支持加边，至于删边的话，可以直接逆序暴力删

然后你就做完了

小事故 : 由于使用随机数据，所以第二部分不需要 LCT 暴力也可以跑过去，看你们的自觉性了…

时间复杂度 : $O(N\log^2N)$

Code

B path

首先你需要知道你要求的答案是图上有多少个点，满足删除这个点之后 $u, v$ 不连通 ($u, v$ 是询问的两个端点)

你就会发现满足条件的点都是割点

再想到 Tarjan 算法

然后就不会了

然后你就会想起有一种叫做圆方树的东西 (其实就是用一个方点代表一个点双联通分量，这个方点向所有点双上的圆点连边)

最后你发现答案就是 $u, v$路径上圆点的数量

做完了

Code

C gemo

这个就是比赛说明里面的那个改个题面变正解的题目

原题 Pkuwc2018 day2 T3

首先你会发现这个题目需要求期望，还要取模，所以肯定不可做

首先你需要看到题目说明里面最坏情况就是走过所有关键点至少一次

分层图高斯消元

我们设 $f[i][S]$表示到达节点 $i$，已经经过了集合 $S$内的关键点的期望，那么显然有
$$f[i][S] = \frac{1}{d_i}\sum_{(i, j)\in E}f[j][S’]+1$$

我们可以发现上面的转移方程式 $S$一定是 $S’$的子集，所以我们可以对 $S’$分层高斯消元

我们可以首先将所有点全部标记为关键点，做一次高斯消元

那么每一次询问相当于有一部分节点不是关键点，我们就认为那么节点已经经过了，
我们发现答案就是 $f[s][S’]$，其中 $S’$为关键点的补集

预处理时间复杂度:$O(2^NN^3)$，询问 $O(1)$

Code

max-min 容斥

首先你需要知道什么是 max-min 容斥

$$max{S}=\sum_{S’\subset S}(-1)^{|S’|-1}min{S’}$$

然后要求的就从起点到达所有关键点的中最晚到达的点的时间期望，变成了到达集合中所有点最早到达的时间
期望

那么现在的问题就变成了给出一个集合，求从 $s$出发到达其中一个点的期望，高斯消元即可

这个过程是 $O(2^NN^3)$的

剩下的就是要合并所有的集合

我会枚举子集

FWTDP 即可

CF 上的 blog

时间复杂度是 $O(2^NN^3+2^NN^2+M)$

Code