AcWing 1153. 括号树
原题链接
中等
作者:
wzc1995
,
2019-11-25 06:35:53
,
所有人可见
,
阅读 1693
算法
(DFS + 栈) $O(n)$
- 考虑统计以每个结点作为末尾的合法子串的个数
t[i]
,即合法的后缀子串,这样最终答案 k[i]
就是当前结点到根结点所有 t[i]
的和。
- 求
t[i]
的过程可以用递推的思想,配合栈的数据结构。我们在深度优先遍历的过程中,如果当前结点为左括号,当前结点的编号进栈;如果为右括号且栈不空,则可以取出栈顶的编号,和当前结点配对。配对后,当前结点的 t[i]
就是 t[fa[top]] + 1
( t[fa[top]]
是以 fa[top]
为结尾的合法子串的个数,这些子串都可以作为 (top, ..., i)
的前缀,(top, ..., i)
本身也是一个合法的后缀子串。
- 递归结束前,恢复之前的栈结构(恢复现场)。
时间复杂度
空间复杂度
C++ 代码
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <vector>
const int N = 500010;
#define LL long long
using namespace std;
int n;
char s[N];
int fa[N];
vector<int> g[N];
stack<int> st;
int t[N];
LL k[N];
void solve(int u) {
int top = -1;
if (s[u] == '(') {
st.push(u);
} else {
if (!st.empty()) {
top = st.top();
t[u] = t[fa[st.top()]] + 1;
st.pop();
}
}
k[u] = k[fa[u]] + t[u];
for (int v: g[u])
solve(v);
if (s[u] == '(') {
st.pop();
} else {
if (top != -1)
st.push(top);
}
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 2; i <= n; i++) {
scanf("%d", &fa[i]);
g[fa[i]].push_back(i);
}
solve(1);
LL ans = 0;
for (int i = 1; i <= n; i++)
ans ^= i * k[i];
cout << ans << endl;
return 0;
}
我终于……终于……看懂了!
讲的太清晰了,方法也很好 %%%
讲的好啊!
tql!!!
太强了,比我的简洁多了,orz