思路:简单题

树上删除一个点之后联通块的个数和他所连的边有关，也就是点的度 . 联通块个数 = 度。所以记录一下有多少个点的度 = 2.

代码

c++代码

1000ms

Difficulty: 1

算法与标签>树

塔子哥是一个喜欢探险的小男孩，有一天，他在森林里发现了一棵奇怪的树。这棵树的枝干和叶子都是紫色的，而且上面还有许多闪闪发光的水晶。

塔子哥觉得这棵树非常美丽，就想把它带回家。但是他发现，这棵树非常沉重，而且很难拔出来。他只好用剪刀剪下一些枝干和叶子，放在他的背包里。

回到家后，塔子哥把他收集的树枝和叶子摆在桌子上，发现它们竟然还能连在一起，形成一个小型的树状结构。

他觉得很有趣，就开始用不同的方式拼接它们。他发现，如果他选择一个点，把它和它连接的所有枝干和叶子都拿走，那么剩下的部分就会分成两个部分。

现在塔子哥想知道，有多少种不同的删点方法可以让剩下的部分就会分成两个部分。你能帮帮他吗？

第一行输入为一个正整数 $n$ ，代表树的节点数量

接下来的 $n - 1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表点 $u$ 和点 $v$ 有一条边连接。

$1 \le n \le 10^5$

一个整数，代表删点的方案数。

输入

输出

样例解释

删除 $2$ 号点， $3$ 号点和 $4$ 号点均可。

编辑器加载中…

输入

预期输出（选填）