2025“钉耙编程”中国大学生算法设计暑期联赛（6）（2025杭电多校 6）——钥匙迷宫（dfs序）

题目大意

题目大意

给定一棵包含 $2n$ 个节点的树，树上分布着 $n$ 种钥匙（编号 $1$ 到 $n$）和 $n$ 种锁（编号 $1$ 到 $n$）。每种钥匙和每种锁在树上恰好出现一次。

节点信息由数组 $a$ 给出：

• 若 $a_i > 0$，表示该节点拥有编号为 $a_i$ 的钥匙。

• 若 $a_i < 0$，表示该节点拥有编号为 $-a_i$ 的锁。

移动与收集规则

1. 出发点：必须选择一个拥有钥匙的节点作为起点。

2. 钥匙获取：到达（或经过）拥有钥匙的节点时，自动获得该钥匙。钥匙永久保留。

3. 通行限制：只有当手中拥有编号为 $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

源代码

// 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 了。

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 时，我们直接开摆即可。

// 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 了。