P16786 [蓝桥杯 2026 国 A] 安全路径

在一个安全网络中，有 $n$ 个通信基站。它们通过 $n-1$ 条双向光纤连接，并形成一棵树。 本题以基站 $1$ 作为整棵树的根。对于任意基站 $x$, 若以 $x$ 为根的子树中包含的基站总数为偶数, 则称基站 $x$ 为一个平稳基站。这里的子树包含基站 $x$ 本身。 对于两个不同的基站 $x$ 和 $y$, 若从 $x$ 到 $y$ 的简单路径上经过的所有基站都是平稳基站, 则称有序路径 $x \to y$ 是一条安全路径。 请你计算整棵树中安全路径的总数。 注意, $x \to y$ 与 $y \to x$ 视为两条不同的安全路径。

第一行包含一个正整数 $n$, 表示基站数量。 接下来 $n-1$ 行, 每行包含两个正整数 $u, v$, 表示基站 $u$ 和基站 $v$ 之间有一条双向光纤。 输入保证给定的 $n$ 个基站和 $n-1$ 条光纤构成一棵树。

输出一行, 包含一个整数, 表示安全路径的总数。

### 【样例说明】 以基站 $1$ 为根时: - 基站 $2$ 的子树包含基站 $2,4$, 大小为 $2$; - 基站 $3$ 的子树包含基站 $3,5$, 大小为 $2$; - 基站 $1$ 的子树包含全部 $6$ 个基站。 因此平稳基站为 $1,2,3$。 安全路径共有 $6$ 条: $1 \to 2$, $1 \to 3$, $2 \to 1$, $3 \to 1$, $2 \to 3$, $3 \to 2$。 这些路径经过的所有基站均为平稳基站, 因此满足要求。 ### 【评测用例规模与约定】 对于 $40\%$ 的数据, 保证 $n \le 500$。 对于所有数据, 保证 $1 \le n \le 500000$。