Problem10625--洛谷P4395 - [BOI2003] Gem 气垫车

10625: 洛谷P4395 - [BOI2003] Gem 气垫车

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数 
唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。

Input

先给出一个数字 $N\ (N \leq 10,000)$,代表树上有 $N$ 个点。
下面 $N-1$ 行,代表两个点相连。

Output

最小的总权值

Sample 1 Input

10 
7 5 
1 2 
1 7 
8 9 
4 1 
9 7 
5 6 
10 2 
9 3

Sample 1 Output

14

HINT

洛谷P4395

Source/Category