这是一种神奇的做法，通过链的情况推导而来。

我们注意到链的情况下，直接跑一遍就好了。

那么我们把整棵树分为若干条链，对于每条链跑一次 DP。

但是注意到这样计算部分结点的答案会算多。所以我们可以记录下每个结点计算答案的次数最后在减掉或者用一些其他方式来避免这种情况。

此时的时间复杂度最坏可以是 $O(n^2)$ 的，比如这种图：

就能把这种思路卡掉。

所以申请加强数据，link

另附该思路代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int MAXN = 5e5 + 5;
int n, ans, dp[MAXN];
string s;
struct Node{
  int cnt, ans;
}TP[MAXN];
vector<int> g[MAXN], note;
string t;
int check2(){
  int ans = 0;
  for (int i = 0; i <= n + 1; i++){
    dp[i] = 0;
  }
  vector<int> st;
  for (int i = 0; i < t.size(); i++){
    if (t[i] == '('){
      st.push_back(i + 1);
    }else if (st.size()){
      dp[i + 1] = dp[st.back() - 1] + 1;
      st.pop_back();
    }
    ans += dp[i + 1];
    TP[note[i]].cnt++;
    TP[note[i]].ans = ans;
    ::ans ^= note[i] * ans;
  }
  return ::ans;
}
void dfs(int x, int fa){
  note.push_back(x);
  t.push_back(::s[x]);
  for (auto v : g[x]){
    if (v != fa){
      dfs(v, x);
    }
  }
  if (!g[x].size()){
    int t = check2();
  }
  note.pop_back();
  ::t.pop_back();
}
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> s;
  s = ' ' + s;
  for (int i = 2; i <= n; i++){
    int x;
    cin >> x;
    g[x].push_back(i);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; i++){
    if (TP[i].cnt % 2 == 0){
      ans ^= i * TP[i].ans;
    }
  }
  cout << ans;
  return 0;
}