Codeforces Round 1086 (Div. 2)——CF-2208-D2. Tree Orientation (Hard Version) · znzryb
## 题目大意
**题目描述**
有一棵包含 $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` 都会被接受）。
**样例输入**
```
11
4
1000
1111
1010
0001
4
1111
0111
0010
0111
4
0011
0111
0011
0001
4
1000
0110
0010
1111
4
1000
0110
1010
1111
5
10000
01011
00111
00010
00001
5
10000
11000
10101
10111
00001
5
10000
01101
00100
01110
10001
4
1100
0100
0011
0001
4
1110
0100
0010
0101
3
100
111
101
```
**样例输出**
```
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)](/2026/03/14/20260314-9433b243)
这道题目的简单版本确实是比较 easy 的。
[Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)](/2026/03/14/20260314-36fb7a33)
我觉得和这道题目有一点像，**都是要使用这个贪心方法，来解决一些问题**。
具体而言，我们要解决的，就是这个两个循环。我们发现，现在的问题在于，全部的 a，都要把全部的 b 给遍历一遍。这个太耗时耗力了。说白了，这个其实是一个连通性问题，**即根节点 i，能不能通过一个中间点 b，访问到这个 a**？当然，我们可以把
```cpp
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$ **的各个孩子的子树是互不相交的。最大子树的根必定是直系孩子（不可能被更小的子树"遮挡"），所以先处理最大的是安全的**。
```cpp
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$：
1. 将 $i$ 能到达的所有节点按 `cnt_reach` **降序**排列。
1. 初始化一个局部 DSU。
1. 按排好的顺序遍历候选节点 $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)$。
**第四步：验证。** 构造完所有边后：
1. 检查边数是否恰好 $N-1$。
1. 用 DSU 检查是否连通（构成一棵树）。
1. 从每个节点 BFS，重建可达性矩阵 $R$，与输入 `Reach` 逐位比较。不一致则输出 "No"。
### 关键修复点（相比 D1 代码的改动）
1. **用 DSU 替代** $O(N^3)$ **枚举**：这是核心优化。不再对每个候选 $a$ 暴力枚举所有 $b$ 判断 `Reach[b][a]`，而是利用排序 + DSU 在 $O(N^2)$ 内完成。
1. **guard 位置修正**：`guard += cnt_reach[a]` 必须放在 `if (!dsu.same(i,a))` **内部**，只对实际选中的孩子计数。放在外面会对链状合法输入误判为 "No"。
1. **自身 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](https://codeforces.com/contest/2208/submission/366894699)
::: 源代码
```cpp
/**
* 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……）
```cpp
_______________[ Stress test, testcase 6170 INPUT ]_______________
1
4
1101
0100
1111
0001
_______________[ Stress test, testcase 6170 OUTPUT]_______________
No
```