#1369. [Baltic2003]Gem

题目描述

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

输入格式

先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连

输出格式

最小的总权值

样例

样例输入

10   

7 5   

1 2   

1 7   

8 9   

4 1   

9 7   

5 6   

10 2   

9 3   

样例输出

14   

数据范围与提示