Colin recently raised a graph theory problem: MCMMPDNT (Minimum Cost Maximum Matching Problem based on the Depth of Nodes in a Tree).
Given a tree with $$$n$$$ nodes rooted at node $$$1$$$. Define the distance between two nodes as the number of edges on the simple path connecting them. Define the depth of the $$$i$$$-th node as the distance between node $$$i$$$ and the root. It's also guaranteed that, except for depth $$$0$$$, there are an even number of nodes at each depth.
Colin then creates a new undirected graph $$$G$$$ with $$$n$$$ nodes. If node $$$i$$$ and node $$$j\ (i\not=j)$$$ have the same depth on the tree, then there will be an undirected edge in $$$G$$$ connecting node $$$i$$$ and node $$$j$$$, and the weight of that edge is the distance between node $$$i$$$ and node $$$j$$$ on the tree.
For a graph $$$G=(V, E)$$$, a matching $$$M$$$ in $$$G$$$ is a set of pairwise non-adjacent edges; that is, no two edges share common vertices. A maximum matching is a matching that contains the largest possible number of edges. The cost of a matching $$$M$$$ is the sum of the weights of the edges in $$$M$$$. The minimum cost maximum matching is a maximum matching with the minimum cost.
Colin wants to know what the cost of the minimum cost maximum matching in $$$G$$$ is.
The first line contains a single integer $$$n\ (1\le n\le 10^6)$$$, representing the number of nodes on the tree.
For the following $$$n-1$$$ lines, each line contains two integers $$$u_i,v_i\ (1\le u_i, v_i\le n, u_i\not =v_i)$$$, representing an edge of the tree.
It's guaranteed that the input edges form a tree, and except for depth $$$0$$$, there are an even number of nodes at each depth.
A single integer, representing the minimum cost of a maximum matching in $$$G$$$.
71 21 32 42 52 63 7
8
One solution for the minimum cost maximum matching of $$$G$$$ is $$$\{(2,3),(4,5),(6,7)\}$$$, and its cost $$$=2+2+4=8$$$.
