題目大意

給定一棵樹，每個節點有一個括號。對於每個節點 \(i\)，定義 \(s_i\) 為從根節點到 \(i\) 的路徑上所有括號按順序組成的字符串。求每個 \(s_i\) 中互不相同的合法括號子串的個數 \(k_i\)。

思路

首先，\(k_i\) 可以從父節點遞推得到，\(k_i=k_{f_i}+a_i\)。其中 \(a_i\) 為以節點 \(i\) 結尾的合法括號序列數量。因此只要求出每個節點的 \(a\)。

以 ( 為 \(1\) ) 為 \(−1\) 做樹上前綴和，設點 \(u\)
的前綴和為 \(sum_u\)。則以 \(u\) 結尾的合法括號子串的開頭 \(v\) 需要滿足：

1. \(sum_{f_v}=sum_u\)。
2. 對於 \(v\to u\) 這條鏈上的所有點 \(x\)，有 \(sum_x\ge sum_u\)。

在 DFS 過程中開一棵值域線段樹維護 \(1\to u\) 這條鏈上每個 \(sum\) 值對應的最大節點深度。這樣就能找到 \(sum_p<sum_u\) 且深度最大的節點 \(p\)。

設 \(ask(x,y)\) 表示 \(1\to x\) 鏈上 \(sum=y\) 的節點數量。則 \(a_u=ask(f_u,k)-ask(p,k)\)。

第一遍 DFS 求出所有詢問並離線下來。

第二遍 DFS 求出所有點的 \(a\)。

第三遍 DFS 對 \(a\) 做樹上前綴和得到所有點的 \(k\) 即可。

Code

#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define eb emplace_back
#define int long long
using namespace std;
constexpr int N=5e5+5;
struct Query{
    int k,coef,id;
    // k：目標值
    // coef：貢獻係數，1/-1
    // id：貢獻給到的節點
    Query(int _k,int _coef,int _id):k(_k),coef(_coef),id(_id){}
};
struct SegTree{
    int t[N<<3];
    void update(int p,int pl,int pr,int pos,int x){  // 單點修改
        if(pl==pr) return void(t[p]=x);
        int mid=pl+pr>>1;
        if(pos<=mid) update(ls(p),pl,mid,pos,x);
        else update(rs(p),mid+1,pr,pos,x);
        t[p]=max(t[ls(p)],t[rs(p)]);
    }
    int query(int p,int pl,int pr,int l,int r){  // 區間max
        if(l>r) return 0;
        if(l<=pl&&pr<=r) return t[p];
        int mid=pl+pr>>1,a=0;
        if(l<=mid) a=max(a,query(ls(p),pl,mid,l,r));
        if(mid<r) a=max(a,query(rs(p),mid+1,pr,l,r));
        return a;
    }
}sgt;
char s[N];
int sum[N],dep[N],cnt[N<<1],a[N],st[N];
int n,m,ans;
vector<int> g[N];
vector<Query> q[N];
void dfs1(int u){
    int lst=sgt.query(1,1,m,sum[u],sum[u]);
    sgt.update(1,1,m,sum[u],dep[u]); 
    st[dep[u]]=u;
    for(int v:g[u]){
        sum[v]=sum[u]+(s[v]=='('?1:-1);
        dep[v]=dep[u]+1;
        if(s[v]==')'){
            int bound=sgt.query(1,1,m,1,sum[v]-1);
            q[u].eb(sum[v],1,v);
            if(bound) q[st[bound]].eb(sum[v],-1,v);
        }
        dfs1(v);
    }
    sgt.update(1,1,m,sum[u],lst);
}
void dfs2(int u){
    ++cnt[sum[u]];
    for(Query x:q[u]){
        a[x.id]+=x.coef*cnt[x.k];
    }
    for(int v:g[u]) dfs2(v);
    --cnt[sum[u]];
}
void dfs3(int u){
    for(int v:g[u]){
        a[v]+=a[u];
        dfs3(v);
    }
    ans^=u*a[u];
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>s+1;
    m=n<<1;
    rept(i,2,n){
        int x;cin>>x;
        g[x].eb(i);
    }
    g[0].eb(1);
    sum[0]=n,dep[0]=1;  // 為了不出負數，sum統一加上n
    dfs1(0),dfs2(0),dfs3(0);
    cout<<ans;
    return 0;
}