[FJWC2019 Day2] 直径
时间限制:1000MS 内存限制:524288KB
难度: \(4.0\)
-
题目描述
你需要构造一棵至少有两个顶点的树,树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。
我们定义这棵树的直径为,所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中,\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\),那么均为直径。
作为一个构造题,你需要构造一个恰有 \(k\) 个直径的树。可以证明在给定的限制下一定有解。
-
输入格式
一行一个正整数 \(k\),表示你需要构造出一个恰有 \(k\) 个直径的树。
-
输出格式
第一行一个正整数 \(n\),表示你构造的树的点数。
接下来 \(n-1\) 行,每行三个整数 \(i,j,w\),表示一条连接点 \(i\) 和 \(j\) (点的编号为 \(1,2, \cdots, n\))的树边,边权为 \(w\) 。
-
样例输入
1 |
3 |
-
样例输出
1 2 3 4 5 |
5 1 2 2 3 2 2 2 5 3 4 2 2 |
-
样例说明
这只是一种符合题意的输出,可能还有其他输出。在这个输出中,直径为 \((1,5),(3,5),(4,5)\) 。
-
数据规模与约定
注意,你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\) !
对于 \(30pts\) 的数据,\(1\leq k \leq 2000\) ;
对于 \(100pts\) 的数据,\(1\leq k \leq 5 \times 10^6\) 。