「Jump up HIGH!!」
在 Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中，介绍了 Kruskal 算法是如何生成最小生成树的
如果将两个联通块联通的不是边而是点呢？
这就是 Kruskal 重构树
具体来说就是，我们原来是通过一条边将两个联通块相连接的，现在我们新建立一个点，将这两个联通块的根节点连接到这个点上，原来的边权就是这个新建节点的点权，这样执行下来，我们会得到一棵新的树，这个树有以下两个特征
无向图 $G$ 的生成树，就是具有图 $G$ 的所有顶点，但是边数最小的联通子图
更加详细的定义: Wikipedia – 生成树
带权联通无向图的总权值最小的生成树
更加详细的定义: Wikipedia – 最小生成树
这个题目很像 Luogu P2290
但是问题在于，这个里面具有不确定的度数
经过简单的思考，我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中
对于一个带编号的无根树，其 Prufer 序列按以下过程处理
每个 Prufer 序列，都对应唯一的一个带编号的无根树
Continue reading “Prufer序列 入门 — P2290 [HNOI2004]树的计数”题目意思非常简单，给你一张图，然后图中不能选最大相邻点，最后最大的选中的点的权值
很容易想到 没有上司的舞会 这种树形 DP 题目，但是显然，这，并不是一棵树
根据题目可得，每一个人只会有一条出边，即，这张图中，一张节点个数为 $n$ 的联通块，会有 $n$ 条边
环套树没得跑了
即每一个联通块中一定有一条边，删掉后就是树了
设这条边为 $u – v$ 的边，则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案
建双向边判环即可
至于代码中的 xor ，当反向边即可
Continue reading “Luogu P2607 [ZJOI2008]骑士”