根据度数判断是否为一棵树的新证法！
Exscallop64_
·
·
休闲·娱乐
:::info[新人必读]
这种东西好像要在显著位置标记一下，避免误导新人吧。
众所周知树的计数，但是考场上我已经忘了怎么根据度数判树。
这是我感冒头疼时想的，当乐子就行。
给定 n 个结点，每个点的度数为 d_i，判断是否是一棵树。
这不是唐题吗？！考虑是树的时候有什么条件，众所周知树是平面图，那从平面图入手。
约定 s = \sum\limits_{i=1}^{n} d_i，n_1=\sum\limits_{i=1}^{n} [d_i=1]，n_2=\sum\limits_{i=1}^{n} [d_i=2]，原树边数 m，显然 m=\frac{s}{2}。
考虑 V-E+F=2，怎么把度数和 V,E,F 扯上关系？诶，我构建一个新图 G，把树上的每个点 i，在 G 中看成一个大小为 d_i 的环！
考虑树边。初始 G 中所有点都未标记。然后考虑树边 (u,v)，对于 u，任选一个 G 中 u 代表的环上的未标记点 x。v 同理选出 y。然后连边 (x,y) 并标记 x,y。
然后这个图很 intersting，因为原树上任意一个度数 \ge 3 的点都可以围成一个面！特殊处理一度点 n_1、二度点 n_2。
然后手推一下发现：
V=s-n_2\\
E=m+s-n_1-2n_2\\
F=n+1-n_1-n_2
于是：
\begin{aligned}
V-E+F &= s-n_2-m-s+n_1+2n_2+n+1-n_2-n_2\\
&= n+1-\frac{s}{2}\\
&= 2
\end{aligned}
所以 s=2(n-1)，故 \sum d_i=2(n-1) 时才是棵树！
这个证法真是好呀……
诶什么叫树上 m=n-1 所以 \sum d_i=2m=2(n-1)？！