[Baltic2003]Gem

时间限制:2s      空间限制:64MB

题目描述

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


输入格式

先给出一个数字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 


提示

没有写明提示


题目来源

没有写明来源