前言：抽时间做了做这道题，把学长送退役的题。
-----------------
题目大意：定义$()$是合法括号串。如果$A,B$是合法括号串，那么$(AB),AB$为合法括号串。现给定根节点为$1$的一棵树，每个节点有一个括号。定义$s_i$是从根节点到$i$结点的括号串，$k_i$是$s_i$的合法子串，求$1*k_1 xor 2*k_2 xor cdots n*k_n$。
这道题其实实现起来并不难，重要的是思维。我也是想了快一个小时才推出来式子QAQ。
可以发现，合法的括号串模型，无非就三种：
1.$combo$式：$()()()cdots ()$
2.套娃式：$(((((cdots )))))$
3.混合式：$((()()cdots ()()))$
很明显，对于$combo$式，如果末尾再添加一个合法括号串，那么对答案肯定又有很多贡献。我们先来简单推一推式子：
假设先前有$n-1$个连续的合法括号串，现在在末尾添加了一个。
先前的答案：$(n-1)+frac{(n-1)*(n-2)}{2}=frac{n*(n-1)}{2}$
现在的答案：$n+frac{n*(n-1)}{2}=frac{n*(n+1)}{2}$
答案增加了$n$。
这对我们来说是个好消息，因为我们只要记录一下先前连续的合法括号串有多少个，就可以$O(1)$求出现在的答案。
答案是不是开始浮出水面了？
对于套娃和混合式，我们把它当作一个合法括号串，它们里面的答案由先前的递推来解决。
设$sum[i]$表示考虑前$i$个括号其合法的子串数量，$c[i]$表示截止到$i$为止连续的合法括号串数量。如果遇到$($，我们就让它入栈，遇到$)$就统计答案，有递推式：
$sum[now]=sum[fa[now]]+c[fa[st[tot]]]+1,c[now]=c[fa[st[tot]]]+1,tot--$
这样写对于序列没有任何问题，但是遇到树形结构就萎了：树是递归遍历的，用栈来维护可能会改变先前的括号顺序。所以我们要用链表来维护左括号序列。
剩下的就没有什么难的了。注意一些小细节：开long long，注意链表已经是否到头，等等。
代码：
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=500005; int fa[maxn],last[maxn*4],c[maxn],sum[maxn],head[maxn],n,tot,cnt,ans; char ch[maxn]; struct node { int next,to; }edge[maxn]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int from,int to) { edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; } inline void dfs(int now) { sum[now]=sum[fa[now]]; if (ch[now]==')'){ if (last[now]) c[now]=c[last[now]]+1,sum[now]+=c[now]; last[now]=last[last[now]]; } ans^=now*sum[now]; for (int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if (ch[now]=='(') last[to]=now; else last[to]=last[now]; if (ch[now]==')'&&ch[to]=='(') c[to]=c[now]; dfs(to); } } signed main() { n=read(); for (int i=1;i<=n;i++) scanf("%c",&ch[i]); for (int i=2;i<=n;i++) { int x=read(); fa[i]=x;add(x,i); } dfs(1); cout<<ans; return 0; }