#P6946. [2018年5月雅礼集训]树

    ID: 6777 传统题 1000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划树形 DP图论带权二分图匹配交替路Bellman–Ford枚举与搜索路径恢复CF2600

[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 注意,样例输出仅仅是一组可行解,还可能有其他的解是可接受的。

数据规模与约定

  • 对于 10%10\% 的数据,n≤5n\le5。
  • 对于 30%30\% 的数据,n≤10n\le10。
  • 对于 60%60\% 的数据,n≤50n\le50。
  • 对于所有数据,n≤150n\le150,1≤s,t≤n1\le s,t\le n;树的形态用某种方式随机生成。