题解 P5658 【括号树【民间数据】】
Ireliaღ
2019-11-20 13:25:59
**树形dp+回溯**
考场上想到的一个有1丶清奇的思路。
`f[i]`表示从根到$i$的所有合法子串个数，`cnt[i]`表示搜索到当前节点，`'('`的个数减去`')'`的个数等于$i$的，以当前节点为结尾的合法序列个数。不难想到，由于每次搜索到一个`'('`时，数组中的所有元素需要整体向右移动，搜索到一个`')'`时，数组中的所有元素需要整体向左移动，那么就定义一个`zero`变量表示数组的`0`下标在哪。
具体思路可以看代码和注释
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 5e5 + 5;
int n;
char ch[MAXN];
int to[MAXN], nxt[MAXN];
int ecnt, head[MAXN];
LL f[MAXN];
LL cnt[MAXN << 2];//( - )
int zero = 1e6;
void Add(int u, int v) {
ecnt++;
to[ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt;
}
void DFS(int u) {
/*cerr << u << "\n";
for (int i = 0; i <= 5; i++) cerr << cnt[zero + i] << " ";
cerr << "\n";*/
f[u] += cnt[zero];//加入当前节点所有匹配完成的合法串个数
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
f[v] += f[u];//子节点包含当前节点的所有合法串
if (ch[v] == '(') {
LL tmp = cnt[zero - 1];//临时变量回溯用
cnt[zero - 1] = 0;//)比(多的方案非法，推掉
zero--;所有串的个数差+1
cnt[zero + 1]++;//加入只含有当前节点的串
DFS(v);
cnt[zero + 1]--;//回溯
zero++;
cnt[zero - 1] = tmp;
} else {
zero++;//所有串的个数差-1
DFS(v);//只含有一个)的串非法，不用加
zero--;//回溯
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
// freopen("brackets.in", "r", stdin);
// freopen("brackets.out", "w", stdout);
cin >> n;
cin >> &ch[1];
for (int i = 2; i <= n; i++) {
int u;
cin >> u;
Add(u, i);
}
if (ch[1] == '(') cnt[zero + 1]++;//根要是左括号，初始就有一个差为1的串
DFS(1);
/*cerr << "\n";
for (int i = 1; i <= n; i++) cerr << f[i] << " ";
cerr << "\n";*/
LL ans = 0;
for (int i = 1; i <= n; i++) {
ans ^= f[i] * i;
}
cout << ans << "\n";
return 0;
}
```