题目

1153. 括号树
在这里插入图片描述

算法标签: 树形 d p dp dp, 栈

思路

首先将问题简化, 将问题转化为序列, 我们发现每一个右括号匹配的做括号是唯一确定的, 那么就有状态表示 f [ i ] f[i] f[i]表示在前 i i i个集合当中的合法括号序列的集合, 属性就是方案数, 将集合按照最后一个括号是否选择进行划分, 如果包含第 i i i个括号一定是右括号, 如果是左括号无法无法匹配

在这里插入图片描述

将序列推广到树, 可以维护当前括号到根节点的括号序列, 可以使用栈维护序列, 时间复杂度 O ( n ) O(n) O(n)序列最长 5 × 1 0 5 5 \times 10 ^ 5 5×105, 因为是连续的所以位置 j j j是 f [ j − 1 ] − f [ j − 2 ] + 1 f[j - 1] - f[j - 2] + 1 f[j−1]−f[j−2]+1, 也就是求出了以 j j j结尾的合法括号序列的数量

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 5e5 + 10;

int n;
vector<int> head[N];
string s;
int fa[N];
LL f[N];
int stk[N], top;

void add(int u, int v) {
   
	head[u].push_back(v);
}

void dfs(int u) {
   
	if (s[u] == '(') {
   
		stk[++top] = u;
		f[u] = f[fa[u]];
		for (int v : head[u]) dfs(v);
		top--;
	}
	else {
   
		if (!top) {
   
			f[u] = f[fa[u]];
			for (int v : head[u]) dfs(v);
		}
		else {
   
			int tmp = stk[top--];
			f[u] = f[fa[u]] + f[fa[tmp]] - f[fa[fa[tmp]]] + 1;
			for (int v : head[u]) dfs(v);
			stk[++top] = tmp;
		}
	}
}

int main() {
   
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> s;
	s = " " + s;
	for (int i = 2; i <= n; ++i) {
   
		cin >> fa[i];
		add(fa[i], i);
	}

	dfs(1);

	LL res = 0;
	for (int i = 1; i <= n; ++i) res ^= i * f[i];

	cout << res << "\n";
	return 0;
}