CSP-S-2019-D1-T2题解

题面链接-luogu

题解

1.括号序列一定是从父节点传递下来的
如果用sum[i]表示当前节点的累计,用tail[i]表示以当前节点为结尾的合法字串匹配数量
可以得到

注:fa[x]x的父节点

  1. 使用栈储存遍历时的信息
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
75
76
77
#include <bits/stdc++.h>

using namespace std;

#define ll long long //不开ll见

const int maxn = 5e5 + 100;

ll n, tot, ans;
int head[maxn], pre[maxn], tree[maxn]; //链式前向星
int w[maxn], f[maxn]; //w是储存节点括号信息 f是父节点信息
ll tail[maxn], sum[maxn]; //tail,sum见上方
bool v[maxn]; //是否已经遍历
stack<int> q;

void add(int x, int y)
{
tree[++tot] = y;
pre[tot] = head[x];
head[x] = tot;
}

void dfs(int x)
{
int tmp = 0;
if (q.size() && w[q.top()] + w[x] == 0 && w[x] == -1)
//判断是否是合法的
{
//是合法的就将当前tail值更新
tmp = q.top();
q.pop();
v[tmp] = 0;

tail[x] = tail[f[tmp]] + 1;
}
else
q.push(x), v[x] = 1;//否则继续

sum[x] = sum[f[x]] + tail[x];//更新sum

for (int i = head[x]; i; i=pre[i])//继续遍历
dfs(tree[i]);

//复原栈
if (v[x])
q.pop(), v[x] = 0;
if (tmp)
q.push(tmp), v[tmp] = 1;
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
char tmp;
cin >> tmp;
if (tmp == '(')
w[i] = 1;
else
w[i] = -1;
}

for (int i = 2; i <= n; ++i)
{
scanf("%d", &f[i]);
add(f[i],i);
}
//上方全是输入

dfs(1);

for (int i = 1; i <= n; ++i)
ans ^= i * sum[i];//计算答案
cout << ans << endl;
return 0;
}
-------------本文结束,感谢您的阅读-------------