房地产销售好做吗_江苏品牌网站建设电话_搜索引擎优化实验报告_上海还能推seo吗

题目

1153. 括号树

算法标签: 树形$dp$, 栈

思路

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

将序列推广到树, 可以维护当前括号到根节点的括号序列, 可以使用栈维护序列, 时间复杂度$O(n)$序列最长$5\times 10^5$, 因为是连续的所以位置$j$是$f[j-1]-f[j-2]+1$, 也就是求出了以$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;
}