题解：CF2247E Build a Tree

MaxBlazeResFire · 2026-07-19 08:03:49 · 题解

首先 k 必然是偶数。因为对于每一条边，都得从 1 走过去后走回来。

接下来考虑上下界分析。答案下界是 1\sim 2\sim 3\sim\cdots\sim n 的链；上界是 1\sim 3\sim 5\sim\cdots\sim 6\sim 4\sim 2 的反对称结构。

考虑增量法构造。你发现在下界的结构上把 2 每右移一位，答案 +2（移到端点不产生贡献）；然后在获得的 1\sim 3\sim 4\sim 5\sim\cdots\sim n\sim 2 结构上，把 4 每右移一位，答案又 +2（移到端点不产生贡献）。你发现不断这么做下去，刚好就是上界的构造。

于是中间所有贡献就都可以取到了。直接试探出完整挪多少偶数，最后余量一个一个挪即可。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 200005

int n,k,p[MAXN],pos[MAXN],ans[MAXN];

inline int Abs( int x ){ return x < 0 ? -x : x; }

inline void solve(){
    scanf("%lld%lld",&n,&k);
    for( int i = 1 ; i <= n ; i ++ ) p[i] = pos[i] = ans[i] = 0;
    int L = 2 * n - 2,R = 0;
    int l = 1,r = n,now = 1;
    while( l <= r ){
        if( now % 2 ) p[l] = now,l ++;
        else p[r] = now,r --;
        now ++;
    }
    for( int i = 1 ; i <= n ; i ++ ) pos[p[i]] = i;
    for( int i = 1 ; i <= n ; i ++ ) R += Abs( pos[i] - pos[i % n + 1] );
    if( k % 2 || k < L || k > R ){ puts("-1"); return; }
    now = L;
    for( int i = 2 ; i <= n ; i += 2 ){
        int maxd = max( 0ll , ( ( n - i / 2 ) - ( i / 2 ) - 1 ) ) * 2;
        if( now + maxd < k ) now += maxd;
        else{
            int l = 1,r = n; i -= 2;
            for( int j = 1 ; j <= i ; j ++ ){
                if( j % 2 ) ans[l] = j,l ++;
                else ans[r] = j,r --;
            }
            if( i + 1 <= n ) ans[l] = i + 1,l ++;
            if( i + 2 <= n ){
                int rem = ( k - now ) / 2;
                for( int j = i + 3 ; j <= i + 2 + rem ; j ++ )
                    ans[l] = j,l ++;
                ans[l] = i + 2,l ++;
                for( int j = i + 3 + rem ; j <= n ; j ++ )
                    ans[l] = j,l ++;
            }
            for( int i = 1 ; i < n ; i ++ ) printf("%lld %lld\n",ans[i],ans[i + 1]);
            return;
        }
    }
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}

::::