【CSP-S 2019-2】括号树

$O(n^2)$暴力:

DFS一遍,在每个节点暴力求出以它结尾的合法括号子串数目。


$O(n)$正解:

DFS一遍,在每个节点通过递推求出以它结尾的合法括号子串数目。

首先定义$\textrm{match}_v$为节点v的祖先中使得路径上的括号串为合法括号串的深度最浅的节点,换句话说就是从v往上爬最多能爬到哪个节点使得路径为合法括号串;定义$\textrm{ansr}_v$为节点v的祖先中使得路径上的括号串为合法括号串的个数,换句话说就是答案所求的合法括号串中以v结尾的个数。

遍历到节点v时:如果v是左括号直接忽略。如果是右括号则看下它的父亲是不是左括号,如果是则直接和它的父亲匹配,否则和它的父亲上朔的左括号节点的父亲(如果是左括号,否则匹配失败)匹配。

然后根据所匹配到的左括号的父亲判断,如果父亲也存在匹配,则可以继续上朔,即v的match节点为所匹配到的左括号的父亲的match节点。否则v的match节点就是所匹配到的左括号。

v的ansr值就是所匹配到的左括号节点的父亲的ansr值(若存在)加1。

v的最终答案就是它的ansr值加上父亲的ansr值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstring>
#include <stack>
#define MAXN 500005
using namespace std;
struct edge
{
int to, next;
} edges[MAXN];
int head[MAXN], cnt = 0;
void add_edge(int from, int to)
{
edges[cnt].to = to;
edges[cnt].next = head[from];
head[from] = cnt++;
}
// 记match[v]为节点v的祖先中使得路径上的括号串为合法括号串的深度最浅的节点
// 记ans[v]为根到节点v的路径上的括号串的合法子括号串
// 记ansr[v]为根到节点v的路径上的括号串中以v结束的合法子括号串
int n, pa[MAXN], match[MAXN];
long long ansr[MAXN], ans[MAXN];
char s[MAXN];
void dfs(int v)
{
if (s[v] == ')')
{
if (s[pa[v]] == '(') // 直接和上一个字符匹配
{
if (match[pa[pa[v]]]) // 若该字符匹配的左括号的上一个字符仍存在匹配,则继续往上爬
{
match[v] = match[pa[pa[v]]];
ansr[v] = ansr[pa[pa[v]]] + 1;
}
else
{
match[v] = pa[v];
ansr[v] = 1;
}
}
else if (s[pa[v]] == ')' && s[pa[match[pa[v]]]] == '(') // 和上一个字符配对的左括号的上一个字符匹配
{
if (match[pa[pa[match[pa[v]]]]]) // 若该字符匹配的左括号的上一个字符仍存在匹配,则继续往上爬
{
match[v] = match[pa[pa[match[pa[v]]]]];
ansr[v] = ansr[pa[pa[match[pa[v]]]]] + 1;
}
else
{
match[v] = pa[match[pa[v]]];
ansr[v] = 1;
}
}
}
ans[v] = ansr[v] + ans[pa[v]];
for (int i = head[v]; i != -1; i = edges[i].next)
dfs(edges[i].to);
}
int main()
{
memset(head, 0xff, sizeof(head));
cin >> n >> (s + 1);
for (int i = 2; i <= n; i++)
{
cin >> pa[i];
add_edge(pa[i], i);
}
dfs(1);

long long xorsum = ans[1];
for (int i = 2; i <= n; i++)
xorsum ^= i * ans[i];
cout << xorsum << endl;
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/CSP-J-S/2019/11/%E3%80%90CSP-S-2019-2%E3%80%91%E6%8B%AC%E5%8F%B7%E6%A0%91/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.