Circular Spanning Tree

本道題目加深理解樹的性質：

思路：

????????首先考慮什么情況是NO，那么不難想當字符串全是0的時候一定是不行的，因為這樣就構成環了，還有一種情況是1的個數為奇數的時候是不行的，一棵樹中為奇數度的點的個數一定是偶數，可以自己畫幾棵樹證明一下。因為樹的所有點的總度數一定是偶數。

? ? ? ? 那么假設接下來的情況一定可以滿足，首先如果字符串全是1，那么我們可以構造類似菊花圖的方法去解決，剩下的就是包含0的字符串，我們可以選擇一個為0的點作為根，因為此時1的個數一定是偶數個。

我們將根移除后的字符串以如下方式斷開（將字符串認為是循環的）

[0,0,…,1][0,0,…,1]?[0,0,…,1]

共?k?組

從根連出?k?條鏈（偶數），每條鏈順次連接上面一對方括號內的點，這樣就能保證題目的條件滿足。

代碼：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
#define fi first 
#define se second
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n;
string s;
int a[N];void solve(){cin>>n;cin>>s;s = " " + s;for(int i=1;i<=n;i++)a[i] = s[i] - '0';a[0] = a[n];a[n+1] = a[1];int k = 0;bool flag = false;for(int i=1;i<=n;i++){k += a[i];if(a[i] == 1)flag = true;}if(!flag || k % 2 == 1){NO;return;}YES;if(k == n){for(int i=2;i<=n;i++)cout<<1<<" "<<i<<"\n";return;}int root = 0;for(int i=1;i<=n;i++){if(a[i] == 0 && a[i-1] == 1){root = i;break;}}int nw = root % n + 1;while(nw != root){cout<<root<<" "<<nw<<"\n";while(a[nw] != 1){cout<<nw<<" "<<nw%n+1<<"\n";nw = nw % n + 1;}nw = nw % n + 1;}return;
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;cin>>T;while(T--){solve();}return 0;
}