← 返回题目列表

Codeforces · 87/D

D. 美丽的道路

中文机器翻译题面 查看原题

很久以前,亚洲的一些国家发生了内战。

n 个城市中的每一个都想夺取权力。这就是为什么有时一个城市会聚集一支军队并派它去攻打另一个城市。

修路很困难,所以这个国家的道路很少,恰好是 n - 1。而且,沿着这些道路,您可以从任何其他城市到达任何城市。

即使在战争期间,东方人民仍然精神丰富,欣赏自然之美。为了在未来的几个世纪里保留对这场伟大十字军东征的记忆,他们在军队大部分时间行走的道路旁种植了一棵美丽的树。东方人热爱自然,所以如果有几条这样的路,那么每条路都种一棵树。

最近,当战争记录被发现时,很明显,每个城市都互相攻击了一次。总共有 n(n - 1) 次攻击。大家一直在想,那些战争之后,哪条路变得最美丽,也就是哪条路他们种植了最多数量的美丽树木。

输入

第一行包含一个整数n (2 ≤ n ≤ 105),代表城市的数量。接下来的 n - 1 行每行包含三个整数:由第 i 条道路连接的城市 ai、bi (1 ≤ ai, bi ≤ n) 的数量以及军队在该道路上行驶所花费的天数 di (1 ≤ di ≤ 109)。多条道路的长度可能重合。

输出

在第一行打印两个整数——最美丽道路上的美丽树的数量和最美丽道路的数量。在第二行打印最美丽道路的列表,按数字递增的顺序排列。道路按照输入数据中给出的顺序从 1 到 n-1 进行编号。

请不要使用 %lld 说明符在 C++ 中写入 64 位整数。最好使用 cout 流(您也可以使用 %I64d 说明符)。

示例

输入 #1

2
2 1 5

输出 #1

2 1
1

输入 #2

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

输出 #2

16 1
2