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}$。代码/...