P99526

珠宝

难度 6 级 动态规划入门 树形
讨论 统计 0通过 2提交 0%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一棵 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
输出
11

提示

对于 100\% 的数据,1\le n\le 50000。

来源

省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交