题目
P3060 [USACO12NOV]Balanced Trees G
给出一棵树，每个节点一个括号，可能左也可能右，求树上一条合法括号路径的最大嵌套层数。
分析
很容易想到点分治，那么现在问题变成如何拼接路径。
由于这样的路径左右顺序会有影响，于是考虑分开处理，也就是拿两个东西分别记从这里出发，和在这里结束两类路径。
然后维护合法性其实就是很简单，分成两截内部和公共的，内部的直接在枚举路径的时候判断就好了，然后公共的就相当于可以对每一个值开一个桶，储存外面需要的答案即可。
那么外面需要的答案是什么呢？
考虑一个已知合法的括号序列怎么求最大嵌套层数，我们可以发现其实这就是括号栈内数量的历史最大值，于是我们在找路径的时候记录一下就好了。
拼接就是取两个历史最值的最值就好了。
剩下的都很好维护了。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=2e5+5;
int n,head[N],nex[N],to[N],idx;
int siz[N],FMax,Root,Size;
int q[N],top,a[N],Max1[N],Max2[N],Ans;
bool vis[N];
char op[5];
inline void add(int u,int v){
nex[++idx]=head[u];
to[idx]=v;
head[u]=idx;
return ;
}
void GetRoot(int x,int fa){
siz[x]=1;int Max=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==fa||vis[y]) continue;
GetRoot(y,x);siz[x]+=siz[y];
Max=max(Max,siz[y]);
}
Max=max(Max,Size-siz[x]);
if(Max<=FMax) FMax=Max,Root=x;
return ;
}
struct Path{int Max1,Max2,Len1,Len2,cnt1,cnt2;}val[N];
void GetPath(int x,int fa){
q[++top]=x;
val[x].Len1+=a[x];
val[x].Max1=max(val[x].Max1,-val[x].Len1);
if(val[x].Len1>0) val[x].cnt1++,val[x].Max1++,val[x].Len1=0;
val[x].Len2+=a[x];
val[x].Max2=max(val[x].Max2,val[x].Len2);
if(val[x].Len2<0) val[x].cnt2++,val[x].Max2++,val[x].Len2=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]||y==fa) continue;
val[y]=val[x];GetPath(y,x);
}
return ;
}
void DFS(int x,int fa){
FMax=Size;GetRoot(x,fa);x=Root;vis[x]=true;
Path now=(Path){0,0,0,0,0,0};
if(a[x]==1) now.cnt1=1;
else now.Len1=-1;
now.Max1=1;
if(!now.Len1) Max1[now.cnt1]=now.Max1;
int Cnt1,Cnt2;
Max2[0]=top=Cnt1=Cnt2=0;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]) continue;
val[y]=now;int tmp=top+1;
GetPath(y,x);
for(int i=tmp;i<=top;i++){
Path res=val[q[i]];
Cnt1=max(Cnt1,res.cnt1),Cnt2=max(Cnt2,res.cnt2);
if(!res.Len1 && ~Max2[res.cnt1]) Ans=max(Ans,max(Max2[res.cnt1],res.Max1));
if(!res.Len2 && ~Max1[res.cnt2]) Ans=max(Ans,max(Max1[res.cnt2],res.Max2));
}
for(int i=tmp;i<=top;i++){
Path res=val[q[i]];
if(!res.Len1) Max1[res.cnt1]=max(Max1[res.cnt1],res.Max1);
if(!res.Len2) Max2[res.cnt2]=max(Max2[res.cnt2],res.Max2);
}
}
for(int i=0;i<=Cnt1;i++) Max1[i]=-1;
for(int i=0;i<=Cnt2;i++) Max2[i]=-1;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==fa||vis[y]) continue;
Size=siz[y],DFS(y,x);
}
return ;
}
signed main(){
read(n);
for(int i=2;i<=n;i++){
int x;read(x);
add(x,i),add(i,x);
}
memset(Max1,-1,sizeof(Max1));
memset(Max2,-1,sizeof(Max2));
for(int i=1;i<=n;i++) scanf("%s",op),a[i]=(op[0]=='('?1:-1);
Size=n,DFS(1,0);
write(Ans);
return 0;
}