题解 P5658 【括号树【民间数据】】
Social_Zhao
·
·
题解
吐槽
看题解区，看到第三页
全是dfs
甚至还有的dalao开栈模拟搜索过程
我就想说：有这么难吗......（本次考试唯一一个AC的题）
正题
首先这题的状态是很好设的。
对于第三个，说明一下：
比如对于这个括号序列：()()()，他其实是由三个()组成的，所以line[i] = 3
那么所有的变量转移如下
如果这个节点是 '(' ，那么f[i]和line[i]直接继承父节点的，last[i]就是i
如果是 ')' ，但last[i]不存在，这个括号就无效了。
如果是 ')' ，且last[i]存在，那么就有以下转移：
-
last[u]=last[fa[last[u]]]$，也就是说$u$和$last[u]$匹配之后上一个没有匹配的就是$last[fa[last[u]]]
-
-
然后去测大样例，然而大样例太臭了，会RE（或者是MLE？）。
这个时候各位大佬就选择了开栈模拟，这固然是一个好方法。
> $u$（$2 \leq u \leq n$）号结点的父亲为 $f_u$（$1 ≤ f_u < u$）
所以说，我们可以直接循环一遍......
# 代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const int N = 5e5 + 5;
int n;
struct Edge { //实测爆栈的铁证
int v, nxt;
} edge[N << 1];
long long head[N], k = 0, fa[N], f[N], ans, last[N], line[N];
char w[N];
/*
inline void addedge(int u, int v) {
edge[++k].v = v;
edge[k].nxt = head[u];
head[u] = k;
}
inline void insedge(int u, int v) {
addedge(u, v), addedge(v, u);
}
*/
inline void file() {
freopen("brackets.in", "r", stdin);
freopen("brackets.out", "w", stdout);
}
int main() {
file();
n = get();
scanf("%s", w + 1);
for(register int i = 2; i <= n; i++) {
fa[i] = get();
//insedge(fa[i], i);
}
for(register int u = 1; u <= n; u++) {
int fath = fa[u];
f[u] = f[fath], last[u] = last[fath];
if(w[u] == '(') last[u] = u;
else if(w[u] == ')' && last[u]) {
line[u] = line[fa[last[u]]] + 1;
last[u] = last[fa[last[u]]];
f[u] += line[u];
}
ans ^= u * f[u];
}
printf("%lld", ans);
return 0;
}
```