直径
题目描述
上午讲了构造题，下午就放一道构造题。你需要构造一棵至少有两个顶点的树，树上的每条边有一个非负整数边权。树上两点 i,ji,ji,j 的距离 dis(i,j)dis(i,j)dis(i,j) 定义为树上连接iii 和 jjj 这两点的简单路径上的边权和。
我们定义这棵树的直径为，所有满足 1≤i<j≤n1leq i<j leq n1≤i<j≤n 的 (i,j)(i,j)(i,j) 中，dis(i,j)dis(i,j)dis(i,j) 最大的。如果有多个这样的 (i,j)(i,j)(i,j)，那么均为直径。
作为一个构造题，你需要构造一个恰有 kkk 个直径的树。可以证明在给定的限制下一定有解。
输入格式
一行一个正整数 kkk，表示你需要构造出一个恰有 kkk 个直径的树。
输出格式
第一行一个正整数 nnn，表示你构造的树的点数。
接下来 n−1n-1n−1 行，每行三个整数 i,j,wi,j,wi,j,w，表示一条连接点 iii 和 jjj （点的编号为1,2⋯n1,2 cdots n1,2⋯n）的树边，边权为 www。
样例
样例输入
3样例输出
5
1 2 2
3 2 2
2 5 3
4 2 2样例解释
这只是一种符合题意的输出，可能还有其他输出。在这个输出中，直径为 (1,5),(3,5),(4,5)(1,5),(3,5),(4,5)(1,5),(3,5),(4,5)。
数据范围与提示
对于所有数据，1≤k≤50000001 leq k leq 50000001≤k≤5000000。
你构造的树需要保证 2≤n≤50002 leq n leq 50002≤n≤5000，且每条边的边权满足 0≤w≤1050 leq w leq 10^50≤w≤105。
Subtask 1（10pts）：1≤k≤51 leq k leq 51≤k≤5。
Subtask 2（20pts）：1≤k≤20001 leq k leq 20001≤k≤2000。
Subtask 3（30pts）：1≤k≤2000001 leq k leq 2000001≤k≤200000。
Subtask 4（20pts）：1+8ksqrt{1+8k}√1+8k 为整数。
Subtask 5（20pts）：无特殊限制。
solution
如果k可以被分解成两个和<5000的数之积，那么就可行
考虑这样的构造
1 2 10
1 3 10
2 a 1
3 b 1
直径数量a*b
现在考虑k不能被分解
我们考虑同上分解成3部分abc
即ab+ac+bc=k
(a+c)(b+c)=k+c*c
那么我们尝试枚举c并尝试分解k+c*c
可以发现不难出解。