好文收藏夹

题解 CF1278E 【Tests for problem D】 @土田共戈 的题解说得很好，但是此题不需要什么启发式合并。 构造策略： 遍历节点  x  的每个儿子，分别处理这些儿子对应的子树。此时这些儿子的右端点尚未确定。 新安排一个位置（ idx++ ），它是  x  的左端点。 逆序遍历 xx 的每个儿子，依次向右安排它们的右端点（ idx++ ）。 具体见代码。 也推荐看@土田共戈 的图解。 # include <bits/stdc++.h> using namespace std ; int N; int lnk[ 500005 ]; int pre[ 1000005 ], tgt[ 1000005 ], cnt; void add_E ( int u, int v) { pre[++cnt] = lnk[u], tgt[cnt] = v, lnk[u] = cnt; } int idx; int ANSL[ 500005 ], ANSR[ 500005 ]; int stk[ 500005 ], len; void DFS ( int x, int f) { for ( int e = lnk[x]; e; e = pre[e]) if (tgt[e] != f) DFS(tgt[e], x); for ( int e = lnk[x]; e; e = pre[e]) if (tgt[e] != f) stk[++len] = tgt[e]; ANSL[x] = ++idx; while (len) ANSR[stk[len]] = ++idx, len--; } int main () { scanf ( "%d" , &N); for ( int i = 1 ; i < N; i++) { int u, v; scanf ( "%d%d" , &u, &v); ad...

题目大意 给出一张无向图以及两个点 a,b ，之后您需要求出有多少对点对 (u,v) 满足从 u 到 v 的任意一条路径都必须同时经过点 a,b 。 同时若 (u,v) 中的任何一个点为 a 或 b ，则这个点对也不合法。 n <= 1e5 吐槽 虽然确实挺有意思，但是这么简单的题，出到 Div2E 我觉得有点不合适吧QAQ。 另外这一篇题解中您可能会大量看见某些词的重复使用。 题解 我们从 a 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 b 。 之后从 b 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 a 。 此时我们应当有三类点：只被 a 染色、只被 b 染色、同时被 a,b 染色，由于图是联通的，所以不会存在没有被染色的点。 答案是第一类点的数量乘上第二类点的数量。 证明 我们考虑一对合法的点 (u,v) ，为方便起见我们假设 u 是第一类点而 v 是第二类点。 之后我们思考一下 u 只被 a 染色的意义是什么。 实际上这意味着 u 可以通过某些方式到达 a ，但它不能通过 a 以外的任何点到达 b ，换句话而言若 u 想有一条到 b 的路径，那么其路径上必须经过 a 。 实际上 v 只被 b 染色的意义是相似的。 之后我们想证明什么？ 我们想证明任何一条从 u 到 v 的路径都必须经过 a,b 。 我们讨论一下一条从 u 到 v 的路径的情况。 实际上我们只需要考虑一下是否可以存在不同时经过 a,b 的路径的可能性就好了。 具体来说，我们假设存在一条路径使得其不经过 b ，那么应当有： 从 v 能不经过 b 到达 u 。 u 能不经过 b 到达 a 。 从 v 能不经过 b 到达 a 于是我们发现此时出现了矛盾，第二类点实际上是不能通过 b 以外的点到达 a 的，于是不可能存在这样一条路径。 证明不存在一条路径使其不经过 a 也可以用相同的方法证明出来。 于是我们就证明了至少有这么多点对是可行的。 之后我们还需要证明其他的点对是不可行的。。 实际上这里的证明和上面的证明也是相似的所以略过。 然后就把这个做法的正确性证明出来了~ 代码 #include   ...

Matrix-Tree定理用于图的生成树计数。复杂度为 O ( n 3 ) O ( n 3 ) . 离散拉普拉斯算子 给定了一个图，我们先求出它的度数矩阵 D D 和邻接矩阵 A A ： 度数矩阵： D[x][x] 表示点 x x 的度数，其它元素为 0 0 . 邻接矩阵： A[i][j] 代表 i i 到 j j 是否有边。有边则为 1 1 ，否则为 0 0 . 由此计算出 基尔霍夫矩阵 C ： C = D − A C = D − A 例子：三个点的完全图： 它的D矩阵（度数矩阵）是： 2 0 0 0 2 0 0 0 2 它的A矩阵（邻接矩阵）是： 0 1 1 1 0 1 1 1 0 它的C矩阵（基尔霍夫矩阵）是： 2 -1 -1 -1 2 -1 -1 -1 2 我们把计算出基尔霍夫矩阵的运算称作 离散拉普拉斯算子 。 Matrix-Tree定理 Matrix-Tree定理的内容是： 对于一个基尔霍夫矩阵，随意去掉第 r 行和第 r 列（ r ∈ [ 1 , n ] r ∈ [ 1 , n ] ），留下的这个矩阵的行列式的 绝对值 ，就是生成树的个数。 一般这样操作：对于一个基尔霍夫矩阵，扔掉最后一行和最后一列，算出它的行列式值即可。 还是看上面的例子。扔掉最后一行和最后一列，C矩阵变成： 2 -1 -1 2 它的行列式值为 2 × 2 − ( − 1 ) × ( − 1 ) = 3 2 × 2 − ( − 1 ) × ( − 1 ) = 3 . 所以这个图共有3个生成树。 行列式求值 如何求行列式的值？ 我们只需要像高斯消元那样，把行列式弄成上三角矩阵，然后算出 C [ 1 ] [ 1 ] × C [ 2 ] [ 2 ] × ⋯ × C [ n ] [ n ] C [ 1 ] [ 1 ] × C [ 2 ] [ 2 ] × ⋯ × C [ n ] [ n ] ，它就是行列式的值。 一个 3 × 3 3 × 3 的例子： 行列式： 2 -1 -1 -1 2 -1 -1 -1 2 第一次消元之后： 2 -1 -1 0 3 -3 0 ...