题解：CF1899F Alex's whims

lailai0916 · 2023-11-20 23:12:47 · 题解

解题思路

如图，用 n-1 个节点构造一条链，根节点为 n-1，叶节点为 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;

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<n-1;i++)cout<<i<<' '<<i+1<<'\n';
        cout<<n<<' '<<2<<'\n';
        int now=2;
        while(q--)
        {
            int d;
            cin>>d;
            if(d==now)cout<<-1<<' '<<-1<<' '<<-1<<'\n';
            else cout<<n<<' '<<now<<' '<<d<<'\n';
            now=d;
        }
    }
    return 0;
}