营地 - 代码源竞赛平台

题目描述

有 $n$ 个营地，由 $n-1$ 条双向道路连成一棵树，营地编号为 $1$ 到 $n$。

清理队选择一条非空简单路径，关闭路径上的全部营地，并移除所有与这些营地相连的道路。如果剩余的每个连通区域都恰好包含奇数个营地，则称这条路径合法。若没有剩余营地，也视为满足条件。

求合法路径的数量。路径可以只包含一个营地；同一条路径从两个相反方向遍历只计数一次。

输入格式

第一行包含一个正整数 $n$，为营地的数量。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，分别为一条双向道路连接的两个营地编号。保证输入的道路构成一棵树。

输出格式

输出一个正整数，表示合法路径的数量。

样例

4
1 2
2 3
3 4

6

1

1

样例解释

样例 1：合法路径的端点对为 $(1,1),(1,3),(1,4),(2,3),(2,4),(4,4)$。

样例 2：关闭唯一的营地后没有剩余营地，因此唯一的路径合法。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$200$	无
$2$	$20$	$2\times 10^5$	A
$3$	$50$		无

特殊性质 A：原树是一条链，即每个顶点的度数均不超过 $2$。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le u,v\le n$，且输入的道路构成一棵无向树。