首页 » 搜索 » 正文

2019年提高组第二题 括号树

合法的括号有两种,以当前节点为最后一个括号,不以当前节点为最后一个括号,f[i]作为从根到i节点的合法括号对数量,g[i]是以i作为括号对最后一个括号的合法括号对数量. 那么就有f[i]=f[parent[i]]+g[i].

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5 * 1e5 + 10;  

typedef long long ll;  

//建树相关的数组 
int h[MAXN], e[MAXN], ne[MAXN],tot=0;  
//父节点数组 
int p[MAXN];  
//栈 
int stk[MAXN], top=0;  
//括号数组,输入的时候从1开始输入 
char str[MAXN];  
//f[i]是根节点到i形成的括号串的合法括号对数量
//g[i]是以i为合法括号对的最后一个,有多少个合法的括号对 
ll f[MAXN], g[MAXN];  

void add(int a, int b){
    e[tot]=b, ne[tot]=h[a], h[a]=tot++;  
}

void dfs(int u){
    //左括号直接入栈,继续进行搜索 
    if(str[u]=='('){
        stk[++top]=u;  
        f[u]=f[p[u]];  
        for(int i=h[u]; ~i; i=ne[i]){
            dfs(e[i]);  
        }
        top--;  
    }
    //右括号 
    else {
        //前面没有可供匹配的左括号,进行继续的搜索 
        if(top==0){
            f[u]=f[p[u]];  
            for(int i=h[u]; ~i; i=ne[i]){
                dfs(e[i]);  
            }
        }
        //先计算以i为最后一个括号有多少种,然后将1. 当前的是合法括号的最后一个
        //2. 当前的不在合法括号串中。 两种进行相加 
        else {
            int t = stk[top--];  
            g[u]=g[p[t]]+1;  
            f[u]=f[p[u]]+g[u];  
            for(int i=h[u]; ~i; i=ne[i]){
                dfs(e[i]);  
            }
            stk[++top]=t;  
        }
    }
}


int main()
{
    memset(h, -1, sizeof(h));  
    int n;  
    scanf("%d", &n);   
    scanf("%s", str+1);  
    for(int i=2; i<=n; i++){
         scanf("%d", &p[i]);  
         add(p[i], i);  
    }
    dfs(1);  
    ll ans=0;  
    for(int i=1; i<=n; i++){
        ans ^=  i*f[i];  
    } 
    cout << ans << endl;  

}
赞 (0)

发表评论