题解：CF1899F Alex's whims

原题链接

• 洛谷 CF1899F Alex's whims

解题思路

如图，用 $n-1$ 个节点构造一条链，根节点为 $n$，叶节点为 $1$。（此处 $n=8$）

让动点 $n$ 与编号为 $k\in[2,n-1]$ 的点相连。

不难发现，节点 $n$ 也是叶节点。

节点 $1$ 到节点 $k$ 的距离为 $k-1$，节点 $k$ 到节点 $n$ 的距离为 $1$，所以节点 $1$ 到节点 $n$ 的距离为 $k$。

通过调整 $k\in[2,n-1]$ 的编号，即可得到距离为 $d\in[2,n-1]$ 的两个叶节点。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=505;
int d[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,q;
		cin>>n>>q;
		for(int i=1;i<=q;i++)
		{
			cin>>d[i];
		}
		for(int i=1;i<=n-2;i++)
		{
			cout<<i<<' '<<i+1<<'\n';
		}
		cout<<n<<' '<<2<<'\n';
		int now=2;
		for(int i=1;i<=q;i++)
		{
			if(d[i]==now)
			{
				cout<<"-1"<<' '<<"-1"<<' '<<"-1"<<'\n';
			}
			else
			{
				cout<<n<<' '<<now<<' '<<d[i]<<'\n';
				now=d[i];
			}
		}
	}
    return 0;
}