CF891D Sloth

懒惰是不好的，对吧？所以我们决定出一道题来惩罚懒人。 给定一棵树，你需要统计有多少种方法可以先删除一条边，再添加一条边，使得最终得到的图仍然是一棵树且拥有一个完美匹配。若两种操作移除的边或添加的边不同，则认为它们是不同的方法。删除的边和添加的边可以相同。 完美匹配是指一个边的子集，使得每个顶点正好被其中一条边覆盖一次。

第一行包含一个整数 $n$（$2 \leq n \leq 5 \cdot 10^{5}$），表示顶点数。 接下来 $n-1$ 行，每行包含两个整数 $a$、$b$（$1 \leq a, b \leq n$），表示一条边的两个端点。保证输入构成一棵树。

输出一个整数，表示满足条件的方法总数。

在第一个样例中，共有 $8$ 种方法： - 删除 $2$ 和 $3$ 之间的边，添加 $1$ 和 $3$ 之间的边； - 删除 $2$ 和 $3$ 之间的边，添加 $1$ 和 $4$ 之间的边； - 删除 $2$ 和 $3$ 之间的边，添加 $2$ 和 $3$ 之间的边； - 删除 $2$ 和 $3$ 之间的边，添加 $2$ 和 $4$ 之间的边； - 删除 $1$ 和 $2$ 之间的边，添加 $1$ 和 $2$ 之间的边； - 删除 $1$ 和 $2$ 之间的边，添加 $1$ 和 $4$ 之间的边； - 删除 $3$ 和 $4$ 之间的边，添加 $1$ 和 $4$ 之间的边； - 删除 $3$ 和 $4$ 之间的边，添加 $3$ 和 $4$ 之间的边。 由 ChatGPT 5 翻译