题解：CF1682D Circular Spanning Tree

LiaoYF · 2025-06-21 12:03:00 · 题解

首先，一棵树的度数和为 2n-2，所以全是 0 或者度数和为奇数就不行。

为了使连出来的是树，我们规定每个点只能向编号比它大的点连 1 条边。n-1 显然只能连 n，然后从 n-2\sim 1 倒着考虑。当前处理的点为 i，如果 i+1 号点还需要连的话，就连 i+1，否则连 n。把所有点按照 1\sim n 排成一排，容易看出这样连出来的边一定不会相交。

但是这样 1 号点永远只能连一条边，如果要求它度数为偶数就不行了。所以我们找到一个度数为奇数的点当作新的 1 号点，沿着环的一圈，给节点重标号即可。

代码

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=200005;
const int MOD=1e9+7,MOD2=998244353;
int n,a[N];
int x;
int id(int u){
    return ((u+x-1)%n?(u+x-1)%n:n);
}
void solve_(){
    cin>>n;
    int s=0;
    x=0;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
        s+=a[i];
        if(a[i]==1)x=i;
    }
    if(s%2||s==0){
        cout<<"NO\n";
        return;
    }
    //debug(x,id(1));
    cout<<"YES\n";
    cout<<id(n-1)<<" "<<id(n)<<"\n";
    a[id(n-1)]=!a[id(n-1)];
    for(int i=n-2;i>=1;i--){
        if(a[id(i+1)]){
            cout<<id(i)<<" "<<id(i+1)<<"\n";
        }else{
            cout<<id(i)<<" "<<id(n)<<"\n";
        }
        a[id(i)]=!a[id(i)];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase,multitest=1;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();
    }
    return 0;
}