洛谷 P5658 括号树（DFS）

题目链接：https://www.luogu.com.cn/problem/P5658

通过数据范围可以发现，这个题的复杂度要控制在O(n)~O(nlogn)之间。

所以对于每一次处理，需要O(logn)，甚至O(1)。对于O(1)的处理，可以直接想一下找规律：

如果一个右括号能匹配左括号，且左括号的前一个括号是一个已经匹配了的右括号，那么就可以将这两个序列合并，当前右括号的贡献等于前一个右括号的贡献加一。如果没有这种情况的话，那么贡献肯定是从1开始的（只于前面的那个左括号有贡献，前面的都会被左括号的前一个所断绝）。

注意回溯。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<stack>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N=500005;
 8 int n;
 9 int head[N],fa[N],tot;
10 char c[N];
11 ll lst[N],ans,sum[N];
12 stack<int> st;
13 struct node{
14     int to,next;
15 }edge[N];
16 void add(int u,int v){
17     edge[tot].to=v;
18     edge[tot].next=head[u];
19     head[u]=tot++;
20 }
21 void DFS(int u){
22     int t=0;
23     if(c[u]==')'){
24         if(!st.empty()){
25             t=st.top();
26             lst[u]=lst[fa[t]]+1;//可以的话，加上原来的贡献，否则贡献就从1开始 
27             st.pop();//直接删去 
28         }
29     }
30     else if(c[u]=='(') st.push(u);
31     sum[u]=sum[fa[u]]+lst[u];
32     for(int i=head[u];i!=-1;i=edge[i].next){
33         int v=edge[i].to;
34         DFS(v);
35     }
36     if(t!=0) st.push(t); 
37     else if(!st.empty()) st.pop();
38 }
39 int main(){
40     memset(head,-1,sizeof(head));
41     scanf("%d",&n);
42     scanf("%s",c+1);
43     for(int i=1;i<n;i++){
44         int u;
45         scanf("%d",&u);
46         add(u,i+1);
47         fa[i+1]=u;
48     }
49     DFS(1);
50     for(int i=1;i<=n;i++) ans^=sum[i]*(ll)i;
51     printf("%lld
",ans);
52     return 0;
53 }

AC代码