CF1899F Alex's whims - CF题解 | 123hh2 = Keep moving forward

# CF1899F Alex's whims

题目链接

要求你构造一课 $n$ 个点的树，并且给出 $q$ 次询问使得

若某次询问可以不进行断边重连操作，则输出 -1 -1 -1 ，否则输出 $u,v_1,v_2$ ，其中 $u和v_1$ 是原先相连的点， $u和v_2$ 是操作后相连的点

由题意可知，构造出的这个树必定满足条件 2，假设给出的 $x$ 等于 $n$ ，那么这个树一定为一条链，我们可以基于这条链来构造

我们首先构造出长度为 $n-1$ 的一条从 $1$ 到 $n-1$ 的链

那么对于任意一个 $x$ ，我们只需要把第 $n$ 个点连接到 $x$ 上，就能构造出长度为 $x$ 的一条简单路径，所以我们只需要维护当前 $n$ 号点连在了哪里即可

显然，最开始 $n$ 号点连在哪里都无所谓，我们只需要保证能够造出有效路径即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}

	signed main()
	{
	int t=read();
	while(t-->0)
	{
	int n=read(),q=read();
	for(int i=1;i<n;i++) cout<<i<<" "<<i+1<<endl;
	int pos=n-1;
	while(q-->0)
	{
	int x=read();
	if(x==pos) {puts("-1 -1 -1");continue;}
	cout<<n<<" "<<pos<<" "<<x<<endl;
	pos=x;
	}
	}
	return _123hh2;
	}