题目大意

给你一个数kkk，请你构造一棵节点数量小于等于5000的直径数量为kkk的树。

我们定义这棵树的直径为，所有满足1≤i

1≤k≤5×106,0≤wi≤1051\leq k\leq 5\times 10^6,0\leq w_i\leq 10^51≤k≤5×106,0≤wi​≤105，wiw_iwi​表示第iii条边的边权。

题解

构造一个菊花图，根节点有三个儿子，每个儿子所在的子树大小分别为a,b,ca,b,ca,b,c且都是一条由权值为0的边组成的链，那么直径为ab+bc+caab+bc+caab+bc+ca。

我们需要令k=ab+ac+bc=(a+c)(b+c)−c2k=ab+ac+bc=(a+c)(b+c)-c^2k=ab+ac+bc=(a+c)(b+c)−c2。

我们可以枚举ccc，将k+c2k+c^2k+c2分解质因数，直到找到合适的(a,b,c)(a,b,c)(a,b,c)即可。

经过计算可以证明有很高的概率存在这样合适的解，实际上对于所有的kkk都如此。

当然，这种方法不一定完全正确，有可能需要四个或更多儿子才能构造出。更好的方法，请看我的另一篇博客。

code

#include
using namespace std;
int n,tot=0,vt=1,fl=0;
struct node{int x,y,z;
}w[10005];
void dd(int v){for(int i=1;i<=v-1;i++){w[++tot]=(node){vt,vt+1};++vt;}
}
int main()
{scanf("%d",&n);for(int a,b,c=1;c<=5000;c++){int v=n+c*c;for(int i=c;i*i<=v;i++){if(v%i>0) continue;a=i-c;b=v/i-c;if(a>=0&&b>=0&&a+b+c+1<=5000){if(a){w[++tot]=(node){1,++vt,1};dd(a);}if(b){w[++tot]=(node){1,++vt,1};dd(b);}if(c){w[++tot]=(node){1,++vt,1};dd(c);}fl=1;break;}}if(fl) break;}printf("%d\n",vt);for(int i=1;i<=tot;i++){printf("%d %d %d\n",w[i].x,w[i].y,w[i].z);}return 0;
}

一些思考

如果wiw_iwi​不能为000，怎么办呢？我们把根节点的每个儿子分别设置对应多个儿子，使得这些儿子没有儿子且到其父亲边权为1即可。