洛谷4606 [SDOI2018]战略游戏
LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把...
标签 虚树 下的文章
- 首页
- 虚树
洛谷4565 [CTSC2018]暴力写挂
LuoguLOJ分析题目中的式子等价于我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。代码// ===============================...
洛谷5891 Fracture Ray
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
洛谷3320 [SDOI2015]寻宝游戏
LuoguLOJ分析通过手玩一些数据可以发现，我们一定会从一个有宝藏的点出发，而且按照 DFS 序遍历所有有宝藏的点会最优。不妨设现有的有宝藏的点按 DFS 序排序后为 $a_1,a_2,a_3,\cdots,a_k$，那么我们要求的就是 $\operatorname{dis}(a_1,a_2)+\operatorname{dis}(a_2,a_3)+\cdots\operatorname{...
CF809E Surprise me!
CodefocesLuogu分析$\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了...首先要知道$f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。其实这题写起来挺休闲的代码// =======...
洛谷3233 [HNOI2014]世界树
LuoguBZOJ分析有个m[1]+m[2]+...+m[q]<=300000的条件，显然是虚树。问题在于怎么DP。首先来两次Dfs，求出虚树上每个点被哪个点控制。然后对于虚树上每一条边$(u,v)$，如果$u$和$v$被同一个点控制，直接把$u$，$v$所属的点的贡献加上这两个点不在虚树中的儿子的大小。否则，倍增求出一个分界点使得上面的点被$u$控制，下面的点被$v$控制，然后分别贡...
洛谷4426 [HNOI2018]毒瘤
LuoguBZOJ分析先把题意转化一下：给定一张有最多$11$条非树边的图，求独立集的方案数。如果是一棵树设$f[i][0/1]$表示以$i$为根的子树，$i$选/不选的方案数。显然有：$\large f[i][0]=\sum\limits_{v\in Son_i}(f[v][0]+f[v][1])$$\large f[i][1]=\sum\limits_{v\in Son_i}f[v][0...
洛谷2495 [SDOI2011]消耗战
LuoguBZOJ分析虚树入门题...先考虑暴力怎么写。设$f[i]$表示以$i$为根的子树中的点全部切断的最小代价，再设$Min[i]$表示$i$到$1$的路径中的最小边权。容易得到：$f[i]=\sum\limits_{v\in Son_{i}}\min\{Min[i],f[i]\}$考虑怎么优化。建出虚树来，把点间最小边权作为虚树上的边权，再按欧拉序跑$\mathrm{DP}$。代码/...