CF1899F Alex's whims

CF1899F Alex’s whims

题目链接

题目大意

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

• 每次询问前可以对这棵树断开一个边并于其他一个点相连使得操作后图的仍为树（条件1）

• 树中存在一条简单路径长度等于每次询问给出的数 $x$（条件2）

若某次询问可以不进行断边重连操作，则输出 -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;
}