F. Alex‘s whims Codeforces Round 909 (Div. 3) 1899F

Problem - F - Codeforces

题目大意：有q次询问，每次询问给出一个数x，要求构造一棵n个点的树，使得对于每次询问，树上都有一条简单路径的长度等于x，同时每次询问前可以对树进行一次操作，即将一个点与其父节点的边断开，然后和其他一个点连边，操作后的图必须仍是一棵树

3<=n<=500;1<=q<=500

思路：通过样例可以发现，如果我们按编号顺序构造一条长度为n-1的链，例如n=5时如下图：

然后对于任意一个询问的数x，我们只需要把n号点连在编号x上即可，这样1到n的距离就等于x，只需维护n号点当前连在哪，如果已经连在x上了，就输出-1-1-1

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll n;
ll a[N];
void init()
{

}
void solve()
{
    cin >> n;
    int q;
    cin >> q;
    init();
    for (int i = 1; i < n; i++)
    {
        cout << i << " " << i + 1 << '\n';
    }
    int now = n - 1;
    for (int i = 1; i <= q; i++)
    {
        int x;
        cin >> x;
        if (x == now)
        {
            cout << "-1 -1 -1\n";
            continue;
        }
        cout << n << " " << now << " " << x << '\n';
        now = x;
    }   
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}