[CQOI2005] 珠宝
题目描述
有一棵 $n$ 个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。
输入输出格式
输入格式
第一行一个整数 $n$。
以下 $n-1$ 行，每行两个数 $u,v(1\le u,v\le n)$，表示 $u$ 和 $v$ 间有一条边。
输出格式
仅一行，为最小编号和。
输入输出样例
输入样例 #1
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8输出样例 #1
11说明
对于 $20\%$ 的数据，$n\le 10$；
对于 $40\%$ 的数据，$n\le 1000$；
对于 $100\%$ 的数据，$1\le n\le 50000$。