2025“钉耙编程”中国大学生算法设计暑期联赛（6）（2025杭电多校 6）——钥匙迷宫（dfs序） · znzryb
## 题目大意
**题目大意**
给定一棵包含 $2n$ 个节点的树，树上分布着 $n$ 种钥匙（编号 $1$ 到 $n$）和 $n$ 种锁（编号 $1$ 到 $n$）。每种钥匙和每种锁在树上恰好出现一次。
节点信息由数组 $a$ 给出：
- 若 $a_i > 0$，表示该节点拥有编号为 $a_i$ 的钥匙。
- 若 $a_i < 0$，表示该节点拥有编号为 $-a_i$ 的锁。
**移动与收集规则**
1. **出发点**：必须选择一个拥有**钥匙**的节点作为起点。
1. **钥匙获取**：到达（或经过）拥有钥匙的节点时，自动获得该钥匙。钥匙永久保留。
1. **通行限制**：只有当手中拥有编号为 $k$ 的钥匙时，才能进入拥有编号为 $k$ 的锁的节点。
**目标**
对于每一种钥匙 $i$（$1 \le i \le n$），判断：如果从拥有钥匙 $i$ 的节点出发，是否能够遍历树的足够多部分，从而收集到全部 $n$ 种钥匙。
**输入格式**
- 第一行包含整数 $T$，表示测试数据组数。
- 每组数据包含：
- 整数 $n$。
- $2n$ 个整数 $a_1, \dots, a_{2n}$，表示节点上的物品。
- $2n-1$ 行，每行两个整数 $u, v$，表示树边。
**输出格式**
对于每组数据，输出一个长度为 $n$ 的 **01字符串**。
- 字符串第 $i$ 个字符对应**编号为** $i$ **的钥匙**作为起点的结果。
- 若能收集所有钥匙输出 `1`，否则输出 `0`。
**样例**
```
Input
4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6
Output
1
011
000
000
```
**样例解释（以第二组数据为例）**
- **配置**：$n=3$。
- 节点 1：锁 3 (-3)
- 节点 2：钥匙 2 (2)
- 节点 3：钥匙 1 (1)
- 节点 4：锁 1 (-1)
- 节点 5：钥匙 3 (3)
- 节点 6：锁 2 (-2)
- 边连接结构：4-2-1-3-6，且 2-5 相连。即 1 是中心，连接 2 和 3；2 连接 4 和 5；3 连接 6。
- **判定过程**：
1. **从钥匙 1 出发（位于节点 3）**：
- 初始拥有：{钥匙 1}。
- 相邻节点：节点 1（锁 3，无钥匙 3，不可入），节点 6（锁 2，无钥匙 2，不可入）。
- 结果：困在节点 3，无法收集所有。对应字符串第 1 位为 **0**。
1. **从钥匙 2 出发（位于节点 2）**：
- 初始拥有：{钥匙 2}。
- 相邻节点：节点 1（锁 3，不可入），节点 4（锁 1，不可入），节点 5（钥匙 3，**可入**）。
- 移动到节点 5，获得钥匙 3。现有：{钥匙 2, 钥匙 3}。
- 回到节点 2，尝试进入节点 1（锁 3）。因有钥匙 3，**可入**。
- 到达节点 1 后，可前往节点 3（钥匙 1，**可入**）。获得钥匙 1。
- 现有：{钥匙 1, 2, 3}。收集完毕。对应字符串第 2 位为 **1**。
1. **从钥匙 3 出发（位于节点 5）**：
- 初始拥有：{钥匙 3}。
- 前往节点 2（钥匙 2，**可入**）。获得钥匙 2。
- 现有：{钥匙 2, 3}。后续过程同上，可收集完毕。对应字符串第 3 位为 **1**。
- **最终输出**：`011`。
## 思路讲解
首先，我们想到暴力，但是跑一次只需要 $O(n)$，也要 $O(n^2)$ 才能跑完。
于是面对这种复杂的问题，我们想到，需要分而治之。
我们先想，如果只有一个钥匙和一个门，那么合法的点在哪里那？
不难发现，肯定是在这边半颗树，也就是有钥匙的子树上的点才是合法的。
那么这个结论是非常显然的，那么现在问题在于我们有非常多的门，其实我们运用一下这个结论就会发现，我们只要不断往门上含有钥匙的子树上走，就行了，最后我们会得到一个联通块，检查一下这个联通块的联通性即可。
## AC代码
[https://vjudge.net/solution/64200130](https://vjudge.net/solution/64200130)
::: 源代码
```cpp
// by Gospel_rock
#include <bitset>
#include <queue>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll maxn = 210;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
struct Node{
ll u;
int isKey;
bool operator<(const Node& o)const {
return isKey<o.isKey;
}
};
struct Solve {
vll A;
vector<vll> g;
vll dir;
vii isOpen;
vii vis;
vll waitKey;
vii hasKey;
// vii visDfs;
Solve() {
cin >> N;
N*=2;
A.resize(N + 5);
g.resize(N + 5);
dir.resize(N + 5);
isOpen.resize(N + 5);
vis.resize(N+5);
waitKey.resize(N+5);
hasKey.resize(N+5);
// visDfs.resize(N+5);
FOR(i, 1, N) { cin >> A[i]; }
FOR(i, 1, N - 1) {
ll u, v;
cin >> u >> v;
g[u].PB(v);
g[v].PB(u);
}
ll door;
FOR(i, 1, N) {
if (A[i] < 0) {
door = i;
break;
}
}
dfsm(door, door);
#ifdef LOCAL
debug(door);
cerr << "dir:";
FOR(i, 1, N) { cerr << dir[i] << " "; }
cerr << "\n";
#endif
dfs(door, door);
priority_queue<Node> pq;
FOR(i,0,SZ(valid)-1){
vis[valid[i]]=true;
pq.push({valid[i],1});
}
while (!pq.empty()) {
auto [u,iskey]=pq.top();
pq.pop();
if (A[u] > 0) hasKey[A[u]] = 1;
if(iskey){
ll key=A[u];
if(waitKey[key]){
vis[waitKey[key]]=true;
pq.push({waitKey[key],0});
}
}
for(auto v:g[u]){
if(vis[v]) continue;
if(A[v]<0){
ll doorVal=abs(A[v]);
if(hasKey[doorVal]){
vis[v]=true;
pq.push({v,0});
}else{
waitKey[doorVal]=v;
}
}else{
vis[v]=true;
pq.push({v,1});
}
}
}
bool ok=true;
FOR(i,1,N){
if(!vis[i]) {ok=false;break;}
}
if(!ok){
FOR(i,1,N/2){
cout<<0;
}
cout<<"\n";
return;
}
vii ans(N/2+5);
FOR(i,0,SZ(valid)-1){
ans[A[valid[i]]]=1;
}
FOR(i,1,N/2){
cout<<ans[i];
}
cout<<"\n";
#ifdef LOCAL
cerr << "valid:";
FOR(i, 0, SZ(valid) - 1) { cerr << valid[i] << " "; }
cerr << "\n";
#endif
}
vll valid;
// return 1 表示的是可以往下走
// return 0 表示不可以往下走
int dfs(ll u, ll fa) {
ll dfsm;
if (A[u] < 0) {
if (dir[u] <= 0)
return 0;
valid.clear();
dfs(dir[u], u);
return 1;
} else {
valid.PB(u);
for (auto v : g[u]) {
if (v == fa)
continue;
int ret=dfs(v, u);
if(ret){
return 1;
}
}
return 0;
}
}
void dfsm(ll u, ll fa) {
ll dfs;
if (A[u] < 0) {
ll doorKind = abs(A[u]);
if (isOpen[doorKind]) {
dir[u] = -1;
}
for (auto v : g[u]) {
if (v == fa)
continue;
dfsm(v, u);
if (!dir[u] && isOpen[doorKind]) {
dir[u] = v;
}
}
} else {
isOpen[A[u]] = true;
for (auto v : g[u]) {
if (v == fa)
continue;
dfsm(v, u);
}
}
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
Solve a;
return 0;
}
/*
hack：
1
3
-3 1 -2 3 2 -1
1 2
4 6
2 3
3 5
2 4
010
hack：
3
7
-1 5 -2 4 -3 3 2 -6 -7 7 6 -4 1 -5
1 3
8 13
1 2
2 4
5 14
4 12
6 10
6 8
4 5
3 6
6 7
5 9
8 11
8
3 -3 -2 7 -7 -1 6 2 -6 -5 8 5 -4 1 -8 4
1 3
1 10
10 12
12 14
1 4
2 7
4 5
1 2
7 13
6 8
4 15
10 16
8 11
8 9
2 6
5
-2 2 4 -3 3 1 -5 5 -4 -1
5 10
2 5
7 8
2 6
1 2
5 7
2 4
2 3
4 9
ans：
0000010
10001000
00001
*/
```
:::
## 心路历程（WA，TLE，MLE……）
那么一开始，我们选择的是纯 dfs 解决该问题，但是 WA 了。
```cpp
vll valid;
void dfs(ll u, ll fa) {
ll dfsm;
if (A[u] < 0) {
if (dir[u] <= 0)
return;
valid.clear();
dfs(dir[u], u);
} else {
valid.PB(u);
for (auto v : g[u]) {
if (v == fa)
continue;
dfs(v, u);
}
}
}
```
主要原因是使用 dfs 时，没有一个全局的信息来参考。
比如下面这组 hack 数据，我的程序会错误地把 2，3 加入 valid 数组中，这个显然是有问题的。
这个其实是因为我们先走了节点 3 这条支路，又走了节点4。
于是我们继续在想，用树上差分固然可以解决此问题，但是总觉得有点杀鸡用牛刀了。使用纯 dfs 方案用办法解决此问题吗？
我们发现这个问题在于我们走完一条路了以后，我们需要知道这条路是封闭的，还是会继续往下走的？**其实只要是会继续往下走的，其他路也不需要走了**。
知道了这个以后，我们发现，其实不用改动很多，仅仅只需要加一个返回值，子树返回值为 1 时，我们直接开摆即可。
```cpp
// return 1 表示的是可以往下走
// return 0 表示不可以往下走
int dfs(ll u, ll fa) {
ll dfsm;
if (A[u] < 0) {
if (dir[u] <= 0)
return 0;
valid.clear();
dfs(dir[u], u);
return 1;
} else {
valid.PB(u);
for (auto v : g[u]) {
if (v == fa)
continue;
int ret=dfs(v, u);
if(ret){
return 1;
}
}
return 0;
}
}
```
然后就 AC 了。