[ICPC 2022 Seoul R] Parentheses Tree

Ghosty_Neutrino · 2025-12-13 13:06:35 · 题解

分析

左括号表示进入一个新节点，深度加 1。

右括号表示离开当前节点，深度减 1。

叶节点对应括号组合，此时该叶节点的深度就是根到它的距离。

遍历字符串，遇到左括号，深度加 1。

如果遇到右括号，先深度减 1，再检查前一个字符是否是左括号，如果是，说明是叶节点，将当前深度加到结果中。

最后输出结果就行。

代码

#include<bits/stdc++.h>
using namespace std;
long long res;
int dep;
string s;
int main(){
    cin>>s;    
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') dep++;
        else{
            dep--; 
            if(s[i-1]=='(') res+=dep;
        }
    }
    cout<<res;
    return 0;
}