题解：P14731 [ICPC 2022 Seoul R] Parentheses Tree

s23261 · 2025-12-13 08:40:28 · 题解

算法分析

要解决这个问题，我们需要根据给定的匹配括号字符串计算有根有序树中所有叶节点到根节点的距离之和。叶节点在括号字符串中表现为连续的 "()"，而每个节点的深度可以通过跟踪括号嵌套层数来确定。

核心思路

括号字符串与树结构的对应关系：每个 "()" 对应一个叶节点，而嵌套的括号表示节点的层级关系。

深度跟踪：通过遍历括号字符串，维护当前深度（嵌套层数）。遇到 "(" 时深度增加，遇到 ")" 时深度减少。

叶节点识别与距离计算：当连续遇到 "()" 时，当前深度减1即为该叶节点到根节点的距离，将此距离累加到总和中。

解释

深度跟踪：遍历字符串时，遇到 "(" 深度加1，遇到")"深度减1。深度代表当前节点所在的层级。

叶节点识别：当连续的 "()" 出现时，说明遇到了一个叶节点。此时的深度减1。

距离累加：将每个叶节点的深度累加到总和中，得到最终结果。

::::success[AC代码]

代码实现

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    long long sum = 0;
    int depth = 0;
    for (int i = 0; i < s.size();  ++i) {
        if (s[i] == '(') {
            depth++;
        } else {
            depth--;
            if (i > 0 && s[i - 1] == '(') { // 检测到"()"，即叶节点
                sum += depth;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

::::