P16786 [Lanquiao Cup 2026 National A] Safe Path

In a secure network, there are $n$ communication base stations. They are connected by $n-1$ bidirectional optical fibers and form a tree. In this problem, base station $1$ is used as the root of the whole tree. For any base station $x$, if the total number of base stations in the subtree rooted at $x$ is even, then base station $x$ is called a stable base station. The subtree here includes base station $x$ itself. For two different base stations $x$ and $y$, if all base stations on the simple path from $x$ to $y$ are stable base stations, then the ordered path $x \to y$ is called a safe path. Please compute the total number of safe paths in the whole tree. Note that $x \to y$ and $y \to x$ are considered two different safe paths.

The first line contains a positive integer $n$, representing the number of base stations. The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is a bidirectional optical fiber between base station $u$ and base station $v$. The input guarantees that the given $n$ base stations and $n-1$ optical fibers form a tree.

Output one line containing an integer, representing the total number of safe paths.

### Sample Explanation When taking base station $1$ as the root: - The subtree of base station $2$ contains base stations $2,4$, with size $2$; - The subtree of base station $3$ contains base stations $3,5$, with size $2$; - The subtree of base station $1$ contains all $6$ base stations. Therefore, the stable base stations are $1,2,3$. There are $6$ safe paths in total: $1 \to 2$, $1 \to 3$, $2 \to 1$, $3 \to 1$, $2 \to 3$, $3 \to 2$. All base stations on these paths are stable base stations, so they meet the requirement. ### Constraints For $40\%$ of the testdata, it is guaranteed that $n \le 500$. For all testdata, it is guaranteed that $1 \le n \le 500000$. Translated by ChatGPT 5