http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1320. Painting(艾雨青)
时间限制:1.0s   内存限制:256.0MB   Special Judge
总提交次数:284   AC次数:55   平均分:40.56
将本题分享到:
   
 
问题描述
  给出一颗n个节点的树,要给每一条边染一个1~n-1的颜色,染颜色i的代价为i,要求同一个节点连出的所有边所染颜色都互不相同,求一个为整棵树染色的方案,使得代价之和尽量小。
输入格式
  第一行一个正整数n
  接下来n-1行,每行两个互不相同的正整数a,b表示节点a与b之间有一条边,保证给出的图是一颗树
输出格式
  第一行一个正整数表示你的方案的总代价
  第二行输出n-1个1~n-1的正整数,分别表示为对应的边所染的颜色
样例输入
3
1 2
1 3
样例输出
3
1 2
数据规模和约定
  此题不要求选手给出最优解,如果选手给出的答案合法且较优即可能有分
  若你给出的方案不合法或权值总和计算不正确,则此测试点不得分
  否则若你的解答为a,参考解答为b
  *若a<=b,该测试点得到5分
  *否则这个测试点你将得到floor(5*(b/a)^N)分
  所有测试点树的形态都是随机生成的
  每个测试点的n的范围如下
TestNTestN
1=511=105
2=1012=110
3=1013=115
4=5014=120
5=5015=125
6=6016=130
7=7017=135
8=8018=140
9=9019=145
10=10020=150