CF888G Xor-MST
Codeforces 分析 这种奇奇怪怪的生成树题考虑 Boruvka 算法。其核心思想是对每个连通块找到最近的连通块，然后合并。 对于这道题，我们考虑把所有数插入到一棵 Trie 中，那么对于每个节点，其左子树和右子树中必定只由一条边相连。这是因为在执行 Boruvka 算法的过程中，必定是左右子树先分别连通，然后再通过一条边合并在一起。 那么我们只需要知道两个数组间两两异或的最小值，将一...
标签 生成树 下的文章
- 首页
- 生成树
洛谷5406 [THUPC2019]找树
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...
洛谷6628 [省选联考 2020 B 卷]丁香之路
Luogu LOJ 分析 走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。 我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。 但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。 时...
UOJ236 【IOI2016】railroad
UOJ Luogu 分析 我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。 既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。 然而欧拉回路还需要连通，所以我们还要求个 ...
LOJ576 「LibreOJ NOI Round #2」签到游戏
LOJ 分析 设 $s_i$ 为 $\sum_{j=1}^i b_j$，则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$，则相当于要让 $(0,n)$ 连通，也就是要求最小生成树。 根据 Kruskal 那套理论，我们一定会连边 $(0,n)$。 根据 Prim 那套理论，剩下的点要么连 $(0,i)$，要么连 $(i,n)$。更具体的，一定存在一个点 $...
洛谷4768 [NOI2018]归程
Luogu 分析 考虑把边按海拔从大到小排序并建 Kruskal 重构树。 每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。 一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。 代码 // ====================...
洛谷2619 [国家集训队]Tree I
Luogu 分析 设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。 考虑 WQS 二分。二分斜率 $m$，则我们需要最小化截距 $b=f(x)-mx$。 把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值，再根据此时最多选出的白边数调整二分上下界即可。 代码 // ==================================== // au...
CF603E Pastoral Oddities
Codeforces Luogu 分析 首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。 证明： 如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。 如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。 于是我们只需要保证图中没有大小为奇数的连通块即可。 ...
BZOJ3714 [PA2014]Kuglarz
BZOJ 分析 设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。 考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。 因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ 间连一条边权为 $...
CF891C Envy
CodeForces 分析 考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。 因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。 现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法：预处理出每条边在加该种边权的边时两端点所在的连通块即可。 代码 //It is made by M_se...