括号数 题解

下面的抑或可以先不管他，我们只要O(n)求出每个$k_i$然后算就是了。

直接求合法串数比较麻烦，我们先固定右端点讨论。

如果右端点是“（”那么答案数是零。

如果是“)”，那么有两种情况，
① (A)

② A1 A2 ...... (An)
考虑用经典的栈来存左括号然后一个一个消，那么某个右括号所匹配的左括号一定是最短的合法串的左端点了，然后如果这个串还要更长的话，此左括号的左边一定是紧接着的另一个合法串。
令dp[i]为以i为右端点的合法串数，
设j为i是右括号情况下匹配的左括号的结点编号，
则
所以当前结点的总方案数ans[i]就等于$^{ans[f_i]}+dp[i]$

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
int read() {
    int f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
    return x * f;
}
LL lmax(LL a,LL b) {
    return a > b ? a : b;
}
LL lmin(LL a,LL b) {
    return a < b ? a : b;
}
vector<int> g[500005];
char c[500005];
LL as[500005];
LL sum[500005];
int f[500005];
int d[500005];
int n,m,i,j,s,o,k;
stack<int> st;
stack<int> ps;
void dfs(int x,int ad) {
    int fa = f[x];
    d[x] = d[fa] + 1;
    sum[x] = sum[fa];as[x] = 0;
    if(c[x] == '(') st.push(x);
    else {
        if(!st.empty()) {
            int p = st.top();
            st.pop();
            ps.push(p);
            ad ++;
            as[x] += as[f[p]] + 1;
        }
        else as[x] = 0;
    }
    sum[x] += as[x];
    for(int i = 0;i < g[x].size();i ++) {
        dfs(g[x][i],ad);
        while(!st.empty() && d[st.top()] > d[x]) st.pop();
        while(ps.size() > ad && d[ps.top()] > d[x]) ps.pop();
        while(ps.size() > ad) st.push(ps.top()),ps.pop();
    }
    return ;
}
int main() {
    n = read();
    scanf("%s",c + 1);
    for(int i = 2;i <= n;i ++) {
        scanf("%d",&s);
        g[s].push_back(i);
        f[i] = s;
    }
    dfs(1,0);
    LL ans = 0;
    for(LL i = 1;i <= n;i ++) {
        ans ^= (i * sum[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

欢迎加入团队