某谷 Rated 比赛泛做
P9534「YsOI2023」广度优先遍历
对于一条非树边，则对应有这两个点的访问顺序的一个偏序，对应到 LCA 的位置就是两条边的偏序。
建出 DAG 拓扑排序即可，时间复杂度 \(O(n\log n)\)，可以做到 \(O(n)\) 但没必要，代码鸽了。
P9535「YsOI2023」连通图计数
非常好题目，爱来自湖南。
\(m=n-1\) 等价于给定度数求树的个数，这是一个经典题，在「HNOI2004」树的计数有描述，即利用 Prufer 序列得到答案为 \(\binom{n-2}{d_1-1,d_2-1,\ldots,d_n-1}\)。
\(m=n\) 即基环树，对于整个大环建立一个虚点，该点向环上的所有点连边，环上的点均不连边，则该图变成一棵树，这棵树所有点的点度同样已经确定，可以直接做，最后再乘上环上点的排列顺序。
注意到建立虚点的过程等价于圆方树中方点的建立，也就是说，该题的基本思路是转成圆方树后计数。
\(m=n+1\)，分两种情况讨论：
- 仙人掌：即两个环并不相交，此时同样建立圆方树，则两方点的度数之和可以得知，暴力枚举一边的度数即可知道所有点的度数，从而套用 \(m=n-1\)，需要减去两个方点相连的情况，此时只需要将两个点绑成一个点，同样跑 \(m=n-1\) 再乘上一个系数即可，因为两方点本质不同，所以还要除以二。
- 一个大的点双，同样建立圆方树，跑一遍 \(m=n-1\) 的情况后剩下的就是计算 \(n\) 个点 \(n+1\) 条边的点双个数，注意到此时的点双一定会有两个度数为 \(3\) 的点，去掉这两个点剩下三条链且至多一条长度为 \(0\)，可以计算得出答案为 \(\binom{n}{2}\frac{(n-2)!(\binom{n}{2}-3)}{3!}\)。
总时间复杂度 \(O(n)\)。
Code