Description
给定一棵树，树的每个节点都有一个左括号或者右括号，求从根节点到每个点简单路径上的括号序列上合法的子括号序列数。
Analysis
显然树形 dp。
考虑如何设计状态，定义 \(f_i\) 表示从 root 到 \(i\) 节点的字串合法数量。
考虑转移，如果当前的括号为左括号，我们无法和前面的括号相匹配，不会对答案产生新的贡献，直接继承 fa 的值即可。
如果当前的括号为右括号，那么根据括号匹配法则，它与左边第一个未匹配的左括号匹配。同时它将对 \(f_u\) 增加 当前所有的合法括号个数 个贡献。（\(f_u\) 初始继承 \(f_{fat_u}\)）
所以，我们定义 \(line_i\) 表示以 \(i\) 为结尾的括号串中合法括号个数，\(last_i\) 表示从 root 到 \(i\) 路径上上一个没被配对的左括号位置。
分类讨论：
-
当前为左括号，则记录 \(last_i=i\)，其余不做处理。
-
当前为右括号，考虑配对，如果无法配对则不做处理。否则 \(last_i=fa_{last_i}\)，\(line_i=line_{fa}+1,f_i=f_{fa}+line_{fa}\)
简单解释，当前括号配对，则从当前节点向前未配对的左括号上移。已经产生的括号个数在它父亲的基础上 +1,对答案新做出的贡献是 \(line_i\)。具体理解可以自己画图，类似于配对的思路。
需要注意一定要先更新完 \(line_i\) 后再更新 \(f\)。原因显然。
非常巧妙的是，本题的树形 dp 没有和平时一样使用记忆化搜索，线性的时间内即可完美解决。
代码如下。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 5e5+5;
char w[N];
int fa[N],last[N],line[N];
int f[N];
int ans = 0;
int n;
signed main()
{
cin>>n;
scanf("%s", w + 1);
for(int i=2;i<=n;i++)
{
cin>>fa[i];
}
for(int u=1;u<=n;u++)
{
int fat = fa[u];
f[u] = f[fat];
last[u] = last[fat];
if(w[u] == '(') last[u] = u;
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];
}
cout<<ans<<endl;
return 0;
}