#P6946. [2018年5月雅礼集训]树
[2018年5月雅礼集训]树
树(tree)
问题描述
燐在地上找到了一棵树,它想把这棵树送给空。不过这棵树看起来太单调了, 燐决定把树上的每条边都染上一种颜色。特别的,燐希望对于每个点,连出的所有边的颜色都互不相同,因为这样可能比较符合乌鸦的审美。给一条边染上颜色 i 的代价是 i,请求出最小代价,并给出任意一种可行的染色方案。
输入格式
从标准输入读入。
第一行为一个正整数 n,代表树的点数。
接下来 n-1 行每行两个正整数 s,t,代表一条边将编号为 s 的点和编号为 t 的点相连。
输出格式
向标准输出写出。第一行为最小代价。
接下来一行 n-1 个正整数,按输入顺序代表每条边的颜色。注意,颜色的权值不能超过 100000。
样例输入1
5
1 2
1 3
2 4
2 5
样例输出1
7
3 1 2 1
样例输出 3
见下发文件 samples/tree/tree3.ans 注意,样例输出仅仅是一组可行解,还可能有其他的解是可接受的。
数据规模与约定
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
- 对于所有数据,,;树的形态用某种方式随机生成。