传送门

题目
更好的阅读体验

题目大意

读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。

分析题目

• 括号字符串中，每一个叶节点都是对应一个 ()；
• 字符串中的深度比实际深度大 $1$，需要减去 $1$ 再进行计算；
• 扫描字符串，遇到 ( 深度 $+1$，否则深度 $-1$；
• 当遇到 () 时，当前的深度 $-1$ 就是根节点到此处的距离；
• 时间复杂度为 $O(n)$ 可以通过此题。

算法步骤

1. 扫描字符串，记为 $s_i$；
2. 对 $s_i$ 作判断，( 和 ) 需要分情况讨论；
3. 如果遇到 (，深度 $+1$，并且，如果下一个字符是 ) 说明找到了叶节点，将 深度-1 记录到答案，需要注意下个字符是否为合法边界；
4. 如果遇到 )，深度 $-1$；
5. 输出答案。

代码

#include <bits/stdc++.h>
#define int long long // 将所有的 int 替换成 long long，否则会爆 int
using namespace std;
string s;
int ans,depth,i;
signed main(){ // 因为 int 会被替换成 long long，但是返回值不允许 long long，所以使用 signed
    cin>>s; // 对应步骤 1
    for(i=0;i<s.length();i++) // 对应步骤 2
        if(s[i]=='('){ // 对应步骤 3 及下面两行
            depth++;
            if(i+1<s.length()&&s[i+1]==')') ans+=depth-1; // 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算
        }else depth--; // 对应步骤 4
    cout<<ans; // 对应步骤 5
}