XI.[USACO12NOV]Balanced Trees G
与上题类似，我们仍然需要分成\(FR\)路径和\(TO\)路径两部分考虑。默认将根归为\(FR\)路径中考虑。
首先是判断怎样搞才是合法的。关于这个，我们可以用一个pair<int,int>来记录全部匹配完后，剩余的)与(的数量，其中first表示)，second表示(。我们设\(fr_x\)表示\(FR\)路径的这一匹配结果，而\(to_x\)表示\(TO\)路径。
则只有first=0的\(FR\)路径与second=0的\(TO\)路径才是合法的。同时，只有fr[u].second=to[v].first时，两条路径才能匹配。
然后就是考虑这括号到底套娃了几层了。
我们令一个\(dpfr_x\)表示\(FR\)路径的套娃数，而\(dpto_x\)表示\(TO\)路径的套娃数。
我们只考虑\(TO\)路径的套娃数求法——因为\(FR\)路径的求法也类似。
任意时刻，to[x].second的值，即为路径最后的那个括号所套的层数。因此当to[x].second增加时，\(dpto_x\)要与其取\(\max\)。（不管这个括号最终能不能匹配完——反正括号不能匹配完时最终也是不合法的路径）
同时，当to[x].second为\(0\)时，如果又来一个右括号，前面所有的括号的套娃层数都会加一，故在此时应令dpto_x++。
\(fr\)的求法与其类似。
最后，我们只需要开一个桶，记录对于所有to[x].first的值，\(dpto_x\)的\(\max\)即可。用fr[x].second从桶中匹配即可。
这题要求的是\(\max\)，而其不具有可减性。因此我们正着跑一遍，然后清空桶并倒着跑一遍即可。复杂度\(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
int n,ROOT,SZ,sz[100100],msz[100100],dpfr[100100],dpto[100100],buc[100100],mx;
pair<int,int>fr[100100],to[100100];
char s[100100];
vector<int>v[100100];
bool vis[100100];
void getsz(int x,int fa){
sz[x]=1;
for(auto y:v[x])if(!vis[y]&&y!=fa)getsz(y,x),sz[x]+=sz[y];
}
void getroot(int x,int fa){
sz[x]=1,msz[x]=0;
for(auto y:v[x])if(!vis[y]&&y!=fa)getroot(y,x),sz[x]+=sz[y],msz[x]=max(msz[x],sz[y]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[ROOT])ROOT=x;
}
void getbra(int x,int fa){
// printf("%d:(%d,%d):%d;(%d,%d):%d\n",x,fr[x].first,fr[x].second,dpfr[x],to[x].first,to[x].second,dpto[x]);
for(auto y:v[x]){
if(vis[y]||y==fa)continue;
dpfr[y]=dpfr[x],dpto[y]=dpto[x],fr[y]=fr[x],to[y]=to[x];
if(s[y]=='('){
if(fr[y].first)fr[y].first--;
else fr[y].second++,dpfr[y]++;
to[y].second++,dpto[y]=max(dpto[y],to[y].second);
}else{
if(to[y].second)to[y].second--;
else to[y].first++,dpto[y]++;
fr[y].first++,dpfr[y]=max(dpfr[y],fr[y].first);
}
getbra(y,x);
}
}
void getread(int x,int fa){
if(!fr[x].first&&buc[fr[x].second]!=-1)mx=max(mx,max(buc[fr[x].second],dpfr[x]));
for(auto y:v[x])if(!vis[y]&&y!=fa)getread(y,x);
}
void getwrite(int x,int fa){
if(!to[x].second)buc[to[x].first]=max(buc[to[x].first],dpto[x]);
for(auto y:v[x])if(!vis[y]&&y!=fa)getwrite(y,x);
}
void geterase(int x,int fa){
if(!to[x].second)buc[to[x].first]=-1;
for(auto y:v[x])if(!vis[y]&&y!=fa)geterase(y,x);
}
void calc(int x){
// printf("ROOT:%d\n",x);
fr[x]=to[x]=make_pair(0,0),dpfr[x]=1,dpto[x]=0;
if(s[x]=='(')fr[x].second++;
else fr[x].first++;
getbra(x,0);
buc[0]=0;
for(int i=0;i<v[x].size();i++)if(!vis[v[x][i]])getread(v[x][i],x),getwrite(v[x][i],x);
geterase(x,0);
buc[0]=0;
for(int i=int(v[x].size())-1;i>=0;i--)if(!vis[v[x][i]])getread(v[x][i],x),getwrite(v[x][i],x);
geterase(x,0);
}
void solve(int x){
calc(x);
getsz(x,0);
vis[x]=true;
for(auto y:v[x])if(!vis[y])ROOT=0,SZ=sz[y],getroot(y,0),solve(ROOT);
}
int main(){
scanf("%d",&n),memset(buc,-1,sizeof(buc));
for(int i=2,x;i<=n;i++)scanf("%d",&x),v[x].push_back(i),v[i].push_back(x);
for(int i=1;i<=n;i++)scanf("%s",s+i);
msz[0]=n+1,SZ=n,getroot(1,0),solve(ROOT);
printf("%d\n",mx);
return 0;
}