2 人解决，2 人已尝试。
3 份提交通过，共有 5 份提交。
8.0 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
The Gem-Toys Company asked you to solve the following problem.
You are given a connected acyclic graph, i.e. a set of vertices connected by edges in such a way that from each vertex you can reach all the other vertices by traversing the edges, and it does not contain a loop.
The Gem-Toys Company is going to produce jewelry models of such graphs. Vertices will be made of gems and edges will be made of gold string. It is required that adjacent vertices are made of different kinds of gems. For each positive integer p there is exactly one kind of gems with the price p.
Your task is to write a program computing the minimal total price of the gems needed to make the model.
The first line of the input contains one positive integer N (1 ≤ N ≤ 10 000), the number of vertices. The vertices are numbered from 1 to N. The following N-1 lines describe the edges, one per line. Each of these lines contains a pair of integers A and B separated by a space (1 ≤ A, B ≤ N, A ≠ B). Such a pair represents an edge connecting vertices A and B.
The first and only line of the output must contain one integer: the minimal total price of the gems needed to make the model.
8 1 2 3 1 1 4 5 6 1 5 5 7 5 8
11
2 人解决，2 人已尝试。
3 份提交通过，共有 5 份提交。
8.0 EMB 奖励。