传送门

题意：构造一棵n个点，k个叶节点的树使得最远的两个叶节点的距离尽可能近。

题解：由于叶节点个数的限制，可以先以1为根，用2到k+1这k个点与1连边，其他的点都塞到这k条边上。如何分配其他的点使最远的两个叶节点尽量近？尽量平均分就行，先往每条边上都加一个，有多的就再加一轮，直到所有点都在树上。

正确性比较显然，也可以反证。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+4;
int n,m,root;
int fa[N];
inline int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*f;
}
int sta[N],tot;
int dis[N];
inline void add(int p,int t) {fa[p]=fa[t];fa[t]=p;++dis[t];
}
int mx,sx;
int main() {n=read(),m=read();root=1;for (int i=1;i<=m;++i) {sta[tot++]=i+1;fa[i+1]=1;dis[i+1]=1;}int cur=1;for (int i=m+2;i<=n;++i) {add(i,sta[cur]);cur=(cur+1)%tot;}for (int i=1;i<=m;++i) {if (mx<dis[i+1]) sx=mx,mx=dis[i+1];else if (sx<dis[i+1]) sx=dis[i+1];}printf("%d\n",sx+mx);for (int i=2;i<=n;++i)printf("%d %d\n",i,fa[i]);return 0;
}