You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 最近提出了一个图论问题：MCMMPDNT（Minimum Cost Maximum Matching Problem based on the Depth of Nodes in a Tree）。

给定一棵 $n$ 个节点的树，其中以节点 $1$ 为根。两个节点的距离定义为连接它们的简单路径上的边数。定义第 $i$ 个节点的深度为节点 $i$ 和根之间的距离。数据可以保证，除了深度 $0$ 之外，每个深度都有偶数个节点。

小 Y 随后创建了一个新的无向图 $G$，其中包含 $n$ 个节点。如果节点 $i$ 和节点 $j\ (i\not = j)$ 在树上具有相同的深度，则 $G$ 中会有一条无向边连接节点 $i$ 和节点 $j$ ，该边的权重是树上节点 $i$ 与节点 $j$ 之间的距离。

对于图 $G=(V，E)$，$G$ 中的匹配 $M$ 是一些顶点不交的边；也就是说，没有两条边连接到同一个顶点。最大匹配是指包含最多的边的匹配。匹配 $M$ 的权是 $M$ 中边的权重之和。

现在的问题是：图 $G$ 的最小权最大匹配的权是多少？

小 Y 试图使用带花树算法（无向图的匹配算法）来解决这个问题，但它似乎太慢了。你能设计一个更快的算法来解决这个问题吗？

输入格式

从 match.in 文件读入数据。

第一行包含一个整数 $n$，表示树上的节点数。

接下来 $n-1$行，每行包含两个整数$u_i，v_i$，表示树的一条边。

保证输入形成一棵树，并且除了深度 $0$ 之外，每个深度都有偶数个节点。

输出格式

输出到 match.out 文件。

一个整数，表示 $G$ 的最小权最大匹配的权。

样例 1

7
1 2
1 3
2 4
2 5
2 6
3 7

8

一个最小权最大匹配是选择 $\{(2,3), (4,5),(6,7)\}$，权为 $=2+2+4=8$。

样例 2

点击链接 ex_match2.in 和 ex_match2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 保证 $1\le n\le 10^6, 1\le u_i,v_i\le n$