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;
}