自动搬运

查看原文

来自洛谷，原作者为

	xiezhiyu **

搬运于2025-08-24 22:00:21，当前版本为作者最后更新于2018-04-19 20:36:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

一句话题意：给定n个点m条有向边，求以1号点为根的树形图数量。

solution：构造有向图基尔霍夫矩阵，求出det(M[1][1])

证明有向图的矩阵树定理：

思路和证明无向图的差不多，构造辅助矩阵。

构造两个矩阵A和B，每列代表一条边x->y。 在A的一列中，第x行为-1，第y行为1，其余是0 在B的一列中，第y行为1，其余为0

A就是按照边的方向定正负的无向图正常的辅助矩阵 B我们把它叫做入度矩阵

这样A*B(T)是基尔霍夫矩阵C： Cij是A的第i行 点乘 B的第i行 i=j时当且仅当边是x->i才有贡献，并且贡献都是1 i!=j时只有i->j时才是-1，否则都是0

设A'为A去掉第1行选n-1列，B'同理

考虑和无向图一样柯西比内，这样相当于选出了n-1条有向边 现在我们考虑哪一些情况可以对最后答案产生贡献。 考虑det(A')=0可以排除掉有环的情况(包括了两点间有两个方向的边) 现在不考虑边的方向的话，剩下有可能做出贡献的是棵树

我们先证 a.当且仅当这是个树形图，且以1为根时det(B')!=0 再证 b.符合这样的情况时det(A')det(B')=1 这样最后的答案就是以1为根的树形图计数了

a. 首先以i为根的树形图相当于i的入度为0，其他每个点入度为1 现在B矩阵中有除1外的n-1个点，有n-1条边对应n-1个列向量，每个有一行为-1

• 如果1号点的入度>0，剩下只有n-2个不为0的数，而B'是个大小为n-1的方阵，行列式的每项需要n-1个数，故det(B')=0

• 1号点的入度为0时，只有1号点可能成为树形图的根，只需要判断是否是树形图。剩下n-1个入度分配给n-1个点，如果不是每个点一个度数，抽屉原理有一个点p入度>=2，B矩阵中对应的两个列向量相同，det(B’)=0

结论：当且仅当它是个以1为根的树形图时，det(A')det(B')!=0

b.

法一：

从叶子往上处理，考虑x->y->z 把x->y的列向量*-1，（也就是第y行为1） 加到y->z的列向量上，把它变成y=1,z=-1 我们发现它把叶节点变成了跟A矩阵一样的形式，行列式的值并没有变 然后一直这样处理直到A'=B', 我们发现自己证出了det(A')=det(B') 所以平方一下det(A')det(B')=1

法二：

显然有det(B')=det(I)=1 按照无向图的方法求det(A')，不需要改边的方向，那么显然det(A')=det(I)=1 复述一下证明过程，从叶子到根处理形如x->y->z的边 把x->y加到y->z上，变成x->y,x->z，此时det不变 最后每条边会变成1->z,而第一行已经被删掉了 剩下的是个单位矩阵，即det(A')=det(I)=1

结论：当它是个以1为根的树形图时，det(A')det(B')=1,否则=0

证明如果有不对的地方请联系我，谢谢~