C26M:Zuma 2

http://poj.openjudge.cn/practice/C26M/

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        int N = 2 * n;

        vector<int> a(N + 1), pos(N + 1);

        for (int i = 1; i <= N; i++) {
            cin >> a[i];
            pos[a[i]] = i;
        }

        int E = N - 1;

        vector<int> head(N + 1, -1);
        vector<int> to(2 * E), nxt(2 * E);
        int ec = 0;

        auto add_edge = [&](int u, int v) {
            to[ec] = v;
            nxt[ec] = head[u];
            head[u] = ec++;
        };

        for (int i = 0; i < E; i++) {
            int u, v;
            cin >> u >> v;
            add_edge(u, v);
            add_edge(v, u);
        }

        bool ok = true;

        vector<int> parent(N + 1, 0);
        vector<int> order;
        order.reserve(N);

        vector<int> st;
        st.reserve(N);

        parent[1] = -1;
        st.push_back(1);

        while (!st.empty()) {
            int u = st.back();
            st.pop_back();

            order.push_back(u);

            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e];

                if (v == parent[u]) continue;
                if (parent[v] != 0) continue;

                parent[v] = u;
                st.push_back(v);
            }
        }

        if ((int)order.size() != N) {
            ok = false;
        }

        vector<unsigned char> need(N + 1, 0);
        vector<int> mate(N + 1, 0);

        if (ok) {
            for (int idx = N - 1; idx >= 0 && ok; idx--) {
                int u = order[idx];

                int cnt = 0;
                int child = 0;

                for (int e = head[u]; e != -1; e = nxt[e]) {
                    int v = to[e];

                    if (parent[v] == u && need[v]) {
                        cnt++;
                        child = v;

                        if (cnt > 1) break;
                    }
                }

                if (cnt > 1) {
                    ok = false;
                } else if (cnt == 1) {
                    mate[u] = child;
                    mate[child] = u;
                    need[u] = 0;
                } else {
                    need[u] = 1;
                }
            }

            if (need[1]) {
                ok = false;
            }
        }

        if (ok) {
            vector<int> stk;
            stk.reserve(N);

            for (int i = 1; i <= N && ok; i++) {
                int x = a[i];
                int y = mate[x];

                int j = pos[y];

                if (j > i) {
                    stk.push_back(j);
                } else {
                    if (stk.empty() || stk.back() != i) {
                        ok = false;
                    } else {
                        stk.pop_back();
                    }
                }
            }

            if (!stk.empty()) {
                ok = false;
            }
        }

        cout << (ok ? "Yes" : "No") << '\n';
    }

    return 0;
}

这是一个关于树的完美匹配（Perfect Matching）与括号序列验证的综合算法题。

题目逻辑解读

树的完美匹配：
- 题目给出了一个拥有 $2 n$ 个节点的树。在树中，如果存在完美匹配，那么这个匹配是唯一的。
- 代码通过“自底向上”的贪心策略寻找匹配：从叶子节点开始，如果一个节点没有被匹配，它必须与其父节点匹配。如果一个节点有多个未匹配的子节点，或者根节点最后未被匹配，则该树不存在完美匹配。
序列合法性验证：
- 题目给出了一个全排列序列 $a$ 。
- 如果树存在唯一完美匹配，我们将每一对匹配的节点 $(u, v)$ 看作是一对括号。
- 合法的序列必须满足：匹配的两个节点在序列中的排布必须符合括号嵌套规则。例如，如果节点 $1$ 和 $2$ 匹配， $3$ 和 $4$ 匹配，序列 [1, 3, 4, 2] 是合法的（嵌套），而 [1, 3, 2, 4] 是不合法的（交叉）。
- 代码使用一个栈（Stack）来验证这种嵌套关系。

Python 代码实现

Python 处理大规模树结构时，需要注意递归深度。这里采用迭代（栈）方式模拟 DFS。

python

import sys

def solve():
    # 使用 generator 快速读取输入，应对大数据量
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    
    T_str = next(it, None)
    if T_str is None: return
    T = int(T_str)
    
    for _ in range(T):
        n = int(next(it))
        N = 2 * n
        
        # 读取排列 a，并记录每个值出现的位置 pos
        a = [0] * (N + 1)
        pos = [0] * (N + 1)
        for i in range(1, N + 1):
            val = int(next(it))
            a[i] = val
            pos[val] = i
            
        # 构建邻接表
        adj = [[] for _ in range(N + 1)]
        for _ in range(N - 1):
            u, v = int(next(it)), int(next(it))
            adj[u].append(v)
            adj[v].append(u)
            
        # 1. 迭代 DFS 获取树的遍历顺序 (order) 和父节点关系
        parent = [0] * (N + 1)
        order = []
        stack = [1]
        parent[1] = -1 # 根节点的父节点标记
        
        while stack:
            u = stack.pop()
            order.append(u)
            for v in adj[u]:
                if parent[v] == 0:
                    parent[v] = u
                    stack.append(v)
        
        if len(order) != N:
            print("No")
            continue

        # 2. 自底向上贪心寻找唯一完美匹配
        ok = True
        need = [False] * (N + 1)
        mate = [0] * (N + 1)
        
        # 逆序遍历 order 即为从叶子向根的方向
        for i in range(N - 1, -1, -1):
            u = order[i]
            unmatched_children = []
            for v in adj[u]:
                if parent[v] == u and need[v]:
                    unmatched_children.append(v)
            
            if len(unmatched_children) > 1:
                ok = False
                break
            elif len(unmatched_children) == 1:
                v = unmatched_children[0]
                mate[u] = v
                mate[v] = u
                need[u] = False # u 已经匹配，不需要父节点了
            else:
                need[u] = True # u 没被子节点匹配，需要父节点来匹配
        
        # 如果根节点 1 还需要匹配，说明匹配失败
        if need[1]:
            ok = False
            
        # 3. 使用栈验证匹配对在序列 a 中的嵌套关系
        if ok:
            stk = []
            for i in range(1, N + 1):
                u = a[i]
                v = mate[u]
                
                # 如果 mate 的位置在后面，说明 u 是左括号
                if pos[v] > i:
                    stk.append(pos[v])
                else:
                    # 如果 mate 的位置在前面，u 是右括号，必须匹配栈顶
                    if not stk or stk[-1] != i:
                        ok = False
                        break
                    stk.pop()
            
            if stk:
                ok = False
                
        print("Yes" if ok else "No")

if __name__ == "__main__":
    solve()

关键点解析

输入效率：
- 使用了 sys.stdin.read().split() 和 iter()。在处理包含大量整数（如 $2 \times 10^{5}$ 个）的题目时，这种方式比多次 input() 快得多。
树的遍历 (Order)：
- 代码先通过一个 DFS 栈得到 order 数组。order 是从根向下的。
- 通过 reversed(order)，我们能确保在处理节点 u 时，它的所有子节点 v 已经处理完毕。这是典型的树形动态规划或贪心算法的预处理方式。
匹配逻辑：
- need[v] 表示节点 v 还没找到匹配的对象。
- 如果节点 u 有一个需要匹配的子节点 v，那么 u 和 v 必须凑成一对。
- 如果有两个以上的子节点都需要 u 匹配，根据“一个节点只能匹配一个”的规则，这棵树就没救了，直接 ok = False。
括号嵌套验证：
- 我们将匹配对 $(u, v)$ 中先出现的那个记为“左括号”，后出现的记为“右括号”。
- 左括号入栈，存储它期望的右括号位置。
- 当遇到右括号时，它必须正好对应当前的栈顶。如果不是（说明发生了交叉），则序列不合法。

复杂度分析

时间复杂度： $O (N)$ 。构图、DFS 遍历、贪心匹配、栈验证全都是线性时间的。
空间复杂度： $O (N)$ 。用于存储邻接表、父节点关系、匹配信息和验证栈。

C26M:Zuma 2 ​

题目逻辑解读 ​

Python 代码实现 ​

关键点解析 ​

复杂度分析 ​

C26M:Zuma 2

题目逻辑解读

Python 代码实现

关键点解析

复杂度分析