TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3220
  • 题目
  • P3220ShadowIterator再战啦啦操
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    啦啦操队形是一棵很大很大的树,它有n个节点,编号1,2,...,n。每条边都有一个长度。
    ShadowIterator指挥者整个啦啦操队形,但是因为这棵树太大了,ShadowIterator每发布一个命令都要花费很多能量才能传到队形的每个位置。ShadowIterator站在r节点,i节点到r节点的距离为dis(i,r),那么ShadowIterator把信息传到i节点的代价是dis(i,r)。信息之间是相互不影响的,即使两条信息同路,也要各自花费各自的能量。
    ShadowIterator很累了,他当然想少用一些能量。可惜啦啦操队形不能修改,于是他决定通过改变自己站的位置来减少能量消耗。你要找出能量消耗最少的节点每次会消耗多少能量,并按编号由小到大输出这些节点的编号。

    输入格式

    第一行一个数n。
    接下来n-1行,每行三个数x,y,z,表示一条边。

    输出格式

    第一行两个数,第一个数是最少能量消耗,第二个数是节点个数。
    第二行输出这些节点的编号。

    样例输入

    6
    1 2 1
    1 3 2
    1 4 3
    4 5 4
    4 6 5

    样例输出

    21 2
    1 4

    提示

    n<=106
    每条路长度不超过106
    输入数据没有负数。


    来源  感谢nodgd命题并提供数据