LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树,因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树,所以我们把问题转化成了求虚树上圆点个数(等价于求点权和)。这个并不好做,但是我们知道边权和是很好求的(等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二),所以可以考虑把...
LuoguLOJ分析题目中的式子等价于我们把一边的点染成黑色,另一边的点染成白色,然后对第二棵树上的这些点建虚树,则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的,不需要卡常就可以过。代码// ===============================...
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边,则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的,所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作,所以可以考虑建虚树,并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
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{...
CodefocesLuogu分析$\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题,报警了...首先要知道$f$ 和 $g$ 都很好转移,同时 $dp$ 也很好转移了。因为 DP 只统计了 $i<j$ 的情况,所以要答案要乘 $2$ ;最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。其实这题写起来挺休闲的代码// =======...
LuoguBZOJ分析有个m[1]+m[2]+...+m[q]<=300000的条件,显然是虚树。问题在于怎么DP。首先来两次Dfs,求出虚树上每个点被哪个点控制。然后对于虚树上每一条边$(u,v)$,如果$u$和$v$被同一个点控制,直接把$u$,$v$所属的点的贡献加上这两个点不在虚树中的儿子的大小。否则,倍增求出一个分界点使得上面的点被$u$控制,下面的点被$v$控制,然后分别贡...
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...
LuoguBZOJ分析虚树入门题...先考虑暴力怎么写。设$f[i]$表示以$i$为根的子树中的点全部切断的最小代价,再设$Min[i]$表示$i$到$1$的路径中的最小边权。容易得到:$f[i]=\sum\limits_{v\in Son_{i}}\min\{Min[i],f[i]\}$考虑怎么优化。建出虚树来,把点间最小边权作为虚树上的边权,再按欧拉序跑$\mathrm{DP}$。代码/...