洛谷4606 [SDOI2018]战略游戏
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
Luogu LOJ 分析 题目中的式子等价于 我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。 虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。 代码 // =======================...
Luogu 分析 对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。 然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。 但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父...
Luogu LOJ 分析 通过手玩一些数据可以发现，我们一定会从一个有宝藏的点出发，而且按照 DFS 序遍历所有有宝藏的点会最优。 不妨设现有的有宝藏的点按 DFS 序排序后为 $a_1,a_2,a_3,\cdots,a_k$，那么我们要求的就是 $\operatorname{dis}(a_1,a_2)+\operatorname{dis}(a_2,a_3)+\cdots\operatorn...
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了... 首先要知道 $f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...