Znzryb's Blog

Educational Codeforces Round 188 (Rated for Div. 2)——CF-2204-D. Alternating Path（无向图下，二分图与没有奇数环是等价的）

Posted on 2026-03-16 Edited on 2026-04-06

题目大意

题目总结

给定一个无向图（无重边、无自环），你要给每条边指定一个方向，得到有向图。

定义一条点序列 $v_1,v_2,\dots,v_k$ （长度可任意大，点可重复）是“交替路径”，当且仅当相邻边方向按如下模式交替：

第 1 条边是 $v_1 \to v_2$ ；
第 2 条边是 $v_3 \to v_2$ ；
第 3 条边是 $v_3 \to v_4$ ；
第 4 条边是 $v_5 \to v_4$ ；
之后继续这样“顺、逆、顺、逆”交替。

一个点 $v$ 被称为“beautiful”，如果在原图中所有从 $v$ 出发的路径（不要求简单路径，允许重复点和边）在你定向后都满足上面的交替性质。

目标：对每个测试用例，求最多能让多少个点成为 beautiful。

输入输出要求（题意层面）

输入有多组测试。
每组给 $n,m$ 和 $m$ 条无向边。
需要输出一个整数：该组图中可成为 beautiful 的点数最大值。

样例

Output
2
4
4
1

样例解释

第 1 组输出 2：最多只能让 2 个点满足“从该点出发的任意路径都交替”。
第 2 组输出 4：图中没有边，任意从点出发的路径都平凡成立，所以 4 个点都可 beautiful。
第 3 组输出 4：最多可让 4 个点满足条件。
第 4 组输出 1：只有 1 个点且无边，因此这个点可 beautiful。

思路讲解

不难发现，有奇数环的环，搞出来一个这个矛盾的方案是非常容易的。

当然，这个是反向论证，我们再正向论证一下，为什么我们一定要求这张图是一个二分图。不难发现，一张图上，一个点要么其所有的边都是出去的，要么所有边都是进去的。

你说你如果违反这一要求会怎么样？那么就会一定不符合这个题设要求（这个应该是非常显然的，因为这样子会导致一个 a→b→c 序列，但是题设要求是 a→b<-c）。

AC代码

源代码

/**
 * Problem: D. Alternating Path
 * Contest: Educational Codeforces Round 188 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2204/problem/D
 * Created: 2026-03-16 23:42:43
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct U_step{
    ll u,step/*,fa*/;
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<char> vis(N+2);
    vector<char> color(N+2);
    ll ans=0;
    for (int i=1;i<=N;++i) {
        if (vis[i]) {
            continue;
        }
        queue<U_step> q;
        q.push({i,1});
        vis[i]=true;
        color[i]=1;
        vector<ll> cnt(2);
        cnt[color[i]]++;
        bool is_erfen=true;
        while (!q.empty()) {
            auto [u,step]=q.front();
            q.pop();
            for (auto v:g[u]) {
                // if (v==fa) continue;
                if (vis[v]) {
                    if (color[v]!=(step+1)%2) {
                        is_erfen=false;
                    }
                    continue;
                }
                vis[v]=1;
                color[v]=(step+1)%2;
                cnt[color[v]]++;
                q.push({v,step+1});
            }
        }
        if (!is_erfen) continue;
        ans+=max(cnt[0],cnt[1]);
        // ans+=(lans+1)/2;
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2204/submission/367015011

1
6 2
1 5
2 3

1
8 9
1 3
1 4
2 3
2 4
5 6
6 7
7 8
8 5
6 8

*/

心路历程（WA，TLE，MLE……）

2026天梯赛选拔赛-L3-1-辉夜的幻想世界

Posted on 2026-03-16 Edited on 2026-04-06

题目大意

题目总结：

给定一个长度为 n 的数组 a。

对任意区间 [l, r]，定义其权值为：

w=\sum_{i=l}^{r}\sum_{j=l}^{r}(a_i \oplus a_j)

其中 ⊕ 表示按位异或。

要求你计算数组中所有非空子区间的权值之和，并对 10^9+7 取模后输出。

输入范围为：

1 ≤ n ≤ 2×10^5
0 ≤ a_i ≤ 10^6

输出一个整数，表示最终答案。

样例：

输入：
6
1 1 4 5 1 4

输出：
422

样例含义：对数组 [1,1,4,5,1,4] 的所有非空子区间分别计算上述双重异或和权值，再把这些权值全部累加，最终结果为 422。

思路讲解

注意，题目中的是非有序对双重求和，所以结果不要忘记乘以一个 2。

vector<vector<ll>> suf_bits(N+2,vector<ll>(26));
vector<vector<ll>> suf_nobits(N+2,vector<ll>(26));
for (ll i=N;i>=1;--i) {
    for (int j=0;j<25;++j) {
      // 注意，我们这里写的是（N-i+1），是指的包含 i 的可以选择的右端点数量
        suf_bits[i][j]=suf_bits[i+1][j]+(A[i]>>j&1)*(N-i+1);
        // (A[i]>>j&1)^1，不要偷懒，不加这个 &1，一定要有 &1 才对
        suf_nobits[i][j]=suf_nobits[i+1][j]+((A[i]>>j&1)^1)*(N-i+1);
    }
}
ll ans=0;
for (int i=1;i<=N;++i) {
    for (int j=0;j<25;++j) {
        if (A[i]>>j&1) {
            ll suf=suf_nobits[i+1][j];
            ll lans=suf%mod*i%mod;
            lans*=(1ll<<j);
            lans%=mod;
            ans+=lans*2;
            ans%=mod;
        }else {
            ll suf=suf_bits[i+1][j];
            ll lans=suf%mod*i%mod;
            lans*=(1ll<<j);
            lans%=mod;
            ans+=lans*2;
            ans%=mod;
        }
    }
}

AC代码

AC
http://10.199.227.101/contest/1005/problem/L3-1/submission-detail/2157

源代码

/**
 * Problem: ${PROBLEM_NAME}
 * Contest: ${PROBLEM_GROUP_NAME}
 * Judge: ${ONLINE_JUDGE_NAME}
 * URL: ${PROBLEM_URL}
 * Created: 2026-03-16 11:05:01
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> suf_bits(N+2,vector<ll>(26));
    vector<vector<ll>> suf_nobits(N+2,vector<ll>(26));
    for (ll i=N;i>=1;--i) {
        for (int j=0;j<25;++j) {
            suf_bits[i][j]=suf_bits[i+1][j]+(A[i]>>j&1)*(N-i+1);
            suf_nobits[i][j]=suf_nobits[i+1][j]+((A[i]>>j&1)^1)*(N-i+1);
        }
    }
    ll ans=0;
    for (int i=1;i<=N;++i) {
        for (int j=0;j<25;++j) {
            if (A[i]>>j&1) {
                ll suf=suf_nobits[i+1][j];
                ll lans=suf%mod*i%mod;
                lans*=(1ll<<j);
                lans%=mod;
                ans+=lans*2;
                ans%=mod;
            }else {
                ll suf=suf_bits[i+1][j];
                ll lans=suf%mod*i%mod;
                lans*=(1ll<<j);
                lans%=mod;
                ans+=lans*2;
                ans%=mod;
            }
        }
    }
    ans%=mod;
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
http://10.199.227.101/contest/1005/problem/L3-1/submission-detail/2157

*/

心路历程（WA，TLE，MLE……）

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

Posted on 2026-03-15 Edited on 2026-04-06

题目大意

给定 $n$ 个人从左到右站成一排。每个人的身份只有两种：诚实者或欺诈者。

诚实者一定说真话。
欺诈者可能说真话，也可能说假话。
第 $i$ 个人会报一个数 $a_i$ ，表示“自己左边有多少个欺诈者”。
额外保证：不存在两个相邻的欺诈者。

任务是统计：一共有多少种身份安排（每个人是诚实者或欺诈者）能够与所有人的发言同时不矛盾。结果对 998244353 取模输出。

输入为两行：

第一行是 $n$ 。
第二行是 $n$ 个整数 $a_i$ 。

输出为一行：满足条件的方案数（取模后）。

样例：

输入：
6
0 0 0 0 0 0

输出：
2

样例含义：6 个人都说自己左边有 0 个欺诈者。在“欺诈者不相邻”的前提下，能成立的身份安排共有 2 种。

思路讲解

// 0 shuo huang
for(int i=1;i<=N;++i){
    if(i==1){
        if(A[i]==0){
            dp[i][1]=1;
            dp[i][0]=1;
        }else{
            dp[i][0]=1;
        }
        continue;
    }
    // 说谎者只能从前面一个的诚实者转移过来
    // 因为不能连续两个都是说谎者
    dp[i][0]=dp[i-1][1];
    if(A[i]==A[i-1]){
      // 可以从诚实者转移过来的条件
        dp[i][1]+=dp[i-1][1];
        dp[i][1]%=mod;
    }
    if(A[i]==A[i-2]+1){
      // 可以从说谎者转移过来的条件
      // 之所以是这个，是因为如果前面一个是说谎者的话，那么再前面一个就是诚实者
        dp[i][1]+=dp[i-1][0];
        dp[i][1]%=mod;
    }
}

AC代码

http://10.199.227.101/contest/1005/problem/L1-7/submission-detail/2146

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]\n";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N;
    cin>>N;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    vector<array<ll,2>> dp(N+2);
    // 0 shu huang
    for(int i=1;i<=N;++i){
        if(i==1){
            if(A[i]==0){
                dp[i][1]=1;
                dp[i][0]=1;
            }else{
                dp[i][0]=1;
            }
            continue;
        }
        dp[i][0]=dp[i-1][1];
        if(A[i]==A[i-1]){
            dp[i][1]+=dp[i-1][1];
            dp[i][1]%=mod;
        }
        if(A[i]==A[i-2]+1){
            dp[i][1]+=dp[i-1][0];
            dp[i][1]%=mod;
        }

    }
    ll ans=dp[N][0]+dp[N][1];
    ans%=mod;
    cout<<ans<<"\n";

    // mod
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*




 */

心路历程（WA，TLE，MLE……）

2026天梯赛选拔赛-赛后总结

Posted on 2026-03-15 Edited on 2026-04-06

基本情况

还是有继续进步的这个空间的。

心得感悟

l1-3（while 写成 if）

l1-5（map 效率不够高）

原来使用了这个 map，对于 2e6 的这个数据，1000ms 的时限，可能不是很够。

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":["<<x<<"]";
#define SZ(x) ((ll)x.size())
#define all(x) x.begin(),x.end()

using namespace std;
using ll = long long;
using DB = double;
const DB pi = acos(-1.0);
//const ll mod = 998244353;
const ll INF = (1ll<<61)-1;
ll lT;

void Solve(){
    ll N,mod;
    cin>>N>>mod;
    vector<ll> A(N+2);
    for(int i=1;i<=N;++i){
        cin>>A[i];
    }
    // map<ll,ll> mp;
    ll ans=0;
    vector<ll> cnt(mod+2);
    for(int i=1;i<=N;++i){
        ll r=A[i]%mod;
        cnt[r]++;
        if (cnt[r]==2) {
            ++ans;
        }
    }
    // for(auto it=mp.begin();it!=mp.end();++it){
    //     if(it->second>=2){
    //         ++ans;
    //     }
    // }
    cout<<ans<<"\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    //	cin>>lT;
    //	while(lT--)
    Solve();
}
/*
AC
http://10.199.227.101/contest/1005/problem/L1-5/submission-detail/2134



 */

l1-7（+，-搞错了）

2026天梯赛选拔赛-L1-7-简单计数（赛时-号搞错成加号了，绷不住了）

l1-9（二分范围设置错误）

http://10.199.227.101/contest/1005/problem/L1-9/submission-detail/2144

赛时 r 写了r=N。（确实是比较搞笑了，因为 n 可能比 diff 小，diff 是一个值，N 是数组大小）

Codeforces Round 1086 (Div. 2)——CF-2208-D2. Tree Orientation (Hard Version)

Posted on 2026-03-15 Edited on 2026-04-06

题目大意

题目描述
有一棵包含 $n$ 个节点的无向树，为了让它更有趣，你对它的 $n-1$ 条边任意指定了方向，将其变成了一棵有向树。
现在你忘记了这棵树的结构和边的方向，但你找到了一份记录，上面写着给边指定方向后，所有节点对之间的可达性。具体来说，给定 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 个字符串的第 $j$ 个字符为 1，则表示在有向树中，节点 $i$ 可以到达节点 $j$ （必然存在一条从 $i$ 到 $j$ 的有向路径）；如果为 0 则表示无法到达。特别地，一个节点总是可以到达它自己。

你的任务是根据这个可达性信息，判断是否存在合法的树结构与边的方向。如果存在，请构造并输出任意一个满足条件的解；如果不存在，请输出 No。本题为 Hard 版本，与 Easy 版本的唯一区别是 $n$ 的数据范围更大。

输入格式
第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ （ $2 \le n \le 8000$ ），表示节点的数量。
接下来 $n$ 行，每行包含一个长度为 $n$ 的 01 字符串，表示可达性矩阵。
保证所有测试用例中 $n^2$ 的总和不超过 $8000^2$ 。

输出格式
对于每个测试用例，如果存在解，输出 Yes，并在接下来的 $n-1$ 行中输出构造的有向边。每行包含两个整数 $x$ 和 $y$ ，表示存在一条从 $x$ 指向 $y$ 的有向边。如果有多个解，输出任意一个即可。
如果不存在解，输出 No。
（输出 Yes 和 No 时不区分大小写，例如 yEs、YES 都会被接受）。

样例输入

样例输出

Yes
2 3
2 4
3 1
No
No
Yes
2 3
4 1
4 2
No
No
Yes
2 1
3 1
3 5
4 3
No
No
Yes
1 2
1 3
4 2
Yes
2 3
3 1

样例解释
对于第一个测试用例，给定的矩阵表示：节点 $1$ 和 $4$ 只能到达它们自己，节点 $2$ 可以到达所有节点，节点 $3$ 只能到达节点 $1$ 和 $3$ 。输出构造的边为 $2 \to 3$ 、 $2 \to 4$ 、 $3 \to 1$ ，这三条边构成了一棵合法的有向树，并且恰好满足上述可达性限制。
对于第二个测试用例，可以证明不存在任何合法的一棵树能够满足给定的可达性要求，因此输出 No。

思路讲解

Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version)

这道题目的简单版本确实是比较 easy 的。

Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)

我觉得和这道题目有一点像，都是要使用这个贪心方法，来解决一些问题。

具体而言，我们要解决的，就是这个两个循环。我们发现，现在的问题在于，全部的 a，都要把全部的 b 给遍历一遍。这个太耗时耗力了。说白了，这个其实是一个连通性问题，即根节点 i，能不能通过一个中间点 b，访问到这个 a？当然，我们可以把

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    for (auto a:nodes) {
        bool ok=true;
        for (auto b:nodes) {
            if (b==a) continue;
            if (Reach[b][a]=='1') {
                ok=false;
                break;
            }
        }
        if (ok) {
            edges.push_back({i,a});
        }
    }
}

我们可以使用离线思想和排序思想，找到一种顺序，使得先处理顺序靠前的，后处理顺序靠后的，不会造成问题。

我们可以按照 cnt_reach（即所有可到达点的数量） 降序排序。

为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。

for (int i=1;i<=N;++i) {
    vector<ll> nodes;
    dsu.init(N);
    for (int j=1;j<=N;++j) {
        if (j==i) continue;
        if (Reach[i][j]=='1') {
            nodes.push_back(j);
        }
    }
    ll guard=0;
    sort(all(nodes),[&](const ll &a,const ll &b) {
        return cnt_reach[a]>cnt_reach[b];
    });
    for (auto a:nodes) {
        // 想恶意卡我？没门
        if (guard>N) {
            cout<<"No\n";
            return;
        }
        if (!dsu.same(i,a)) {
            guard+=cnt_reach[a];
            edges.emplace_back(i,a);
            dsu.merge(i,a);
            for (auto b:node_reach[a]) {
                dsu.merge(i,b);
            }
        }
    }
}

AI对我们做法的总结

虽然我无法访问到当前的文件系统（worktree 似乎已被清理），但根据我们之前的深入讨论和我读过的代码，我可以完整总结我们的做法。

总结：D2. Tree Orientation (Hard Version) 的做法

核心思路

给定一个 $n \times n$ 的可达性矩阵 Reach，要求还原一棵 $n$ 个节点的有向树（ $n-1$ 条边）使得可达性与输入一致。
关键观察：如果 Reach[i][j] = '1'，说明 $i$ 能到达 $j$ 。在有向树中， $i$ 的直系孩子 $c$ 满足： $i$ 能到 $c$ ，且不存在中间节点 $b$ 使得 $i \to b \to \cdots \to c$ 。
D1 的 $O(N^3)$ 做法是暴力三重循环：对每个 $i$ ，枚举候选孩子 $a$ ，再枚举所有其他节点 $b$ 检查 Reach[b][a] 来判断 $a$ 是否被某个 $b$ “遮挡”。

D2 的 $O(N^2)$ 优化

第一步：预处理。 对每个节点 $i$ ，计算 cnt_reach[i]（ $i$ 能到达的节点数，不含自身）和 node_reach[i]（ $i$ 能到达的节点列表）。
第二步：贪心找直系孩子。 对每个节点 $i$ ：

将 $i$ 能到达的所有节点按 cnt_reach 降序排列。
初始化一个局部 DSU。
按排好的顺序遍历候选节点 $a$ ：

若 dsu.same(i, a) 为真，说明 $a$ 已经被某个先前确认的孩子的子树覆盖，跳过。
否则， $a$ 是 $i$ 的一个直系孩子。连边 $(i, a)$ ，然后把 node_reach[a] 中的所有节点 merge 进 $i$ 的 DSU 分量，同时把 $a$ 本身也 merge 进去。
为什么降序排列有效？ cnt_reach 最大的节点，其子树规模最大。在合法树中， $i$ 的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的。
复杂度分析： 对合法输入，每个节点 $i$ 的所有直系孩子的子树大小之和恰好等于 $|R(i)| - 1$ ，即 merge 操作的总量不超过 $O(N)$ 。遍历候选也是 $O(|R(i)|)$ 。因此所有节点加起来是 $O(N^2)$ 。
第三步：防御性 guard。 累加实际被选为孩子的节点的 cnt_reach 值（仅对真正的孩子累加，不是对所有候选节点）。如果这个累加和超过 $N$ ，说明输入矩阵不合法，直接输出 “No”。这个 guard 同时也防止恶意输入把复杂度卡到 $O(N^3)$ 。
第四步：验证。 构造完所有边后：

检查边数是否恰好 $N-1$ 。
用 DSU 检查是否连通（构成一棵树）。
从每个节点 BFS，重建可达性矩阵 $R$ ，与输入 Reach 逐位比较。不一致则输出 “No”。

关键修复点（相比 D1 代码的改动）

用 DSU 替代 $O(N^3)$ 枚举：这是核心优化。不再对每个候选 $a$ 暴力枚举所有 $b$ 判断 Reach[b][a]，而是利用排序 + DSU 在 $O(N^2)$ 内完成。
guard 位置修正：guard += cnt_reach[a] 必须放在 if (!dsu.same(i,a)) 内部，只对实际选中的孩子计数。放在外面会对链状合法输入误判为 “No”。
自身 merge：确认孩子 $a$ 后，除了 merge node_reach[a] 的所有节点，还需要 dsu.merge(i, a) 把 $a$ 本身也并入。

一句话总结

按子树大小降序贪心 + DSU 快速跳过已覆盖节点 + BFS 回代验证，将 D1 的 $O(N^3)$ 传递归约优化为 $O(N^2)$ 。

AC代码

AC
https://codeforces.com/contest/2208/submission/366894699

源代码

/**
 * Problem: D2. Tree Orientation (Hard Version)
 * Contest: Codeforces Round 1086 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2208/problem/D2
 * Created: 2026-03-16 13:00:28
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */


/**   并查集（DSU）
 *    2023-08-04: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63239142 (base on jiangly)
 *    2025-11-08: https://frp-shy.com:32768/domjudge/team H题 增加dsu on next，标记区间l，r的功能
 *    为了适配这个dsu on next，对merge 函数合并方向进行了修改。
 *    2025-12-05：https://codeforces.com/contest/2171/submission/351963922
 *    增加了 countFa 功能
 *    2025-12-23：移除了宏定义，增加功能说明模块。
 *    功能说明：dsu on next，find(x)，就是在 x 之后第一个没有被标记的数字
 *    该 dsu 传入构造函数的这个大小，需要是 n 就是 n，如果你不希望 countFa 出错的话。
**/
struct DSU {
    vector<int> fa/*, siz*/;
    ll n;

    DSU() {}
    DSU(ll n):n(n){
        init(n);
    }

    void init(ll n) {
        n+=5;
        fa.resize(n);
        for(int i=0;i<SZ(fa);++i) {
            fa[i]=i;
        }
        // siz.assign(n, 1);
    }

    ll find(ll x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(ll x,ll y) {
        return find(x) == find(y);
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // siz[y] += siz[x];
        fa[x] = y;
        return true;
    }

    // ll size(ll x) {
        // return siz[find(x)];
    // }

    // dsu on next 技巧，直接标记 [l,r] 这段区间
    // 标记就是指让[l,r]这段区间里的所有数字这个都不指向自己
    // 可以理解为指向 r+1
    void taglr(ll l,ll r) {
        l=max(0ll,l);
        r=min(SZ(fa)-2,r);
        l=find(l);
        while(l<=r) {
            merge(l,l+1);
            l+=1;
            l=find(l);
        }
    }
    // 如果想让 countFa 结果准确，传入的 n 必须不多不少
    ll countFa() {
        ll res=0;
        for(int i=1;i<=n;++i) {
            if (fa[i]==i) {
                ++res;
            }
        }
        return res;
    }
};

void Solve() {
    ll N;
    cin >> N;
    vector<vector<char>> Reach(N+2,vector<char>(N+2));
    vector<vector<int>> node_reach(N+2);
    vector<ll> cnt_reach(N+2);
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=N;++j) {
            cin>>Reach[i][j];
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                cnt_reach[i]++;
                node_reach[i].push_back(j);
            }
        }
    }
    vector<pair<ll,ll>> edges;
    DSU dsu(N);
    for (int i=1;i<=N;++i) {
        vector<ll> nodes;
        dsu.init(N);
        for (int j=1;j<=N;++j) {
            if (j==i) continue;
            if (Reach[i][j]=='1') {
                nodes.push_back(j);
            }
        }
        ll guard=0;
        sort(all(nodes),[&](const ll &a,const ll &b) {
            return cnt_reach[a]>cnt_reach[b];
        });
        for (auto a:nodes) {
            // 像恶意卡我？没门
            if (guard>N) {
                cout<<"No\n";
                return;
            }
            if (!dsu.same(i,a)) {
                guard+=cnt_reach[a];
                edges.emplace_back(i,a);
                dsu.merge(i,a);
                for (auto b:node_reach[a]) {
                    dsu.merge(i,b);
                }
            }
        }
        // for (auto a:nodes) {
        //     bool ok=true;
        //     for (auto b:nodes) {
        //         if (b==a) continue;
        //         if (Reach[b][a]=='1') {
        //             ok=false;
        //             break;
        //         }
        //     }
        //     if (ok) {
        //         edges.push_back({i,a});
        //     }
        // }
    }
    do {
        DSU dsu_check(N);
        if (SZ(edges)!=N-1) {
            cout<<"No\n";
            return;
        }
        vector<vector<ll>> g(N+2);
        for (auto [u,v]:edges) {
            dsu_check.merge(u,v);
            g[u].push_back(v);
        }
        // 对化为无向图后，树的可达性作校验
        if (dsu_check.countFa()!=1) {
            cout<<"No\n";
            return;
        }
        // 直接模拟，校验我们所构造
        vector<vector<char>> R(N+2,vector<char>(N+2,'0'));
        for (int i=1;i<=N;++i) {
            queue<ll> q;
            q.push(i);
            R[i][i]='1';
            while (!q.empty()) {
                ll a=q.front();
                q.pop();
                for (auto v:g[a]) {
                    if (R[i][v]=='1') {
                        continue;
                    }
                    R[i][v]='1';
                    q.push(v);
                }
            }
        }
        for (int i=1;i<=N;++i) {
            for (int j=1;j<=N;++j) {
                if (Reach[i][j]!=R[i][j]) {
                    cout<<"No\n";
                    return;
                }
            }
        }
    }while (false);

    cout<<"Yes\n";
    for (auto [u,v]:edges) {
        cout<<u<<" "<<v<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}


/*
AC
https://codeforces.com/contest/2208/submission/366894699

1
4
1000
1111
1010
0001

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No

*/

心路历程（WA，TLE，MLE……）

_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001

_______________[ Stress test, testcase 6170 OUTPUT]_______________
No

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

基本情况

心得感悟

l1-3（while 写成 if）

l1-5（map 效率不够高）

l1-7（+，-搞错了）

l1-9（二分范围设置错误）

题目大意

思路讲解

虽然我无法访问到当前的文件系统（worktree 似乎已被清理），但根据我们之前的深入讨论和我读过的代码，我可以完整总结我们的做法。

总结：D2. Tree Orientation (Hard Version) 的做法

核心思路

D2 的 O(N2)O(N^2)O(N2) 优化

关键修复点（相比 D1 代码的改动）

一句话总结

AC代码

心路历程（WA，TLE，MLE……）

D2 的 $O(N^2)$ 优化