自动搬运

查看原文

来自洛谷，原作者为

	balalida ？

搬运于2025-08-24 21:44:53，当前版本为作者最后更新于2021-12-06 22:34:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

人生中第一次写洛谷题解。

是一道板子+细节题，如果想要调试的可以去最下方获得 Hack 数据。

题目大意

给你一个括号树，求匹配括号中的最大嵌套。

题解

最大嵌套是非常经典的。

对于一个括号序列，每个 ( 看作 +1，每个 ) 看作 -1，那么最大嵌套就是这个括号序列的前缀最大值。

这是一个路径统计问题，可以选用的工具有点分治、dsu on tree 以及线段树合并，此题使用点分治。

每次考虑经过分治重心的路径，一定可以拆成左边的一段以及右边的一段。

那么所谓“最大前缀和”在这条链上体现的就是“左边链的最大前缀和”与“右边链的最大前缀和加上左边的和”。（可以理解成线段树的经典套路。）

因为对于每一个根到另外一个节点的路径不分左右，也就是前后缀无法区分，那么我们就定向：从根到各个节点。

好，那么我们的任务就明确了：在统计每个子树时，记录每一条根到节点的链的后缀最大值（供给左边的链，下称左链），以及前缀最大值（共给右链）。

我们的思路时：在 dfs 过程中统计每种链作为左链或者右链的贡献（即最大值）。

就这样开始了，问题也来了。

一些定义：

Warning：建议在自己画括号折线图+理解。

ldis:表示当前这条链以左端点作为基准点，右端点的位置（可能为负）。

rdis:表示当前这条链以右端点作为基准点，左端点的位置（可能为负）。

lmx:表示当前这条链的最大后缀。

rmx:表示当前这条链（包括根节点）的最大前缀。

lmn:表示当前这条链以左端点作为基准点，最低点的位置。

rmn:表示当前这条链以右端点作为基准点，最低点的位置。

第一个细节：根节点

这是个简单的问题，直接默认根节点给右链，也就是在dfs的初始值设定时放上根节点，而作为左链的时候不变

第二个细节：判断是否合法

其实点分治的核心也在于此：开一个桶 $b_i$，表示左链失配括号个数为 $i$ 的最大前缀和。

那么每次使用一条右链来和左链匹配，那么答案用 $\max(b[ldis_i],ldis_i+rmx_j)$ 更新。

那么如果左链或右链甚至自己都不合法了怎么办？

交给 dfs！

第三个细节：dfs怎么写

好问题。 lmn 和 rmn 会发挥用场了。

显然，只有在他们都 =0 的时候（为什么不是大于等于?）才成立。

那么在 dfs 的过程中记录每一条合适做左链和右链的 mx 与 dis 即可。

那么儿子的转移时比较显然的，不说了。

不过注意在转移 rmx 的时候注意不是和 0 取 max ，因为此时表示的时儿子的状态，并非父亲的。

代码

void Grt(ll u,ll fa){
	sz[u]=1;ll mx=0;
	go(u)if(v!=fa&&!vis[v])Grt(v,u),sz[u]+=sz[v],mx=max(mx,sz[v]);
	mx=max(mx,TRsz-sz[u]);
	if(mx<szRT)szRT=mx,RT=u;
}
void dfs(ll u,ll fa,ll ldis,ll rdis,ll lmx,ll rmx,ll lmn,ll rmn){
	if(lmn>=0)tmp1[++kkk1]=ldis,tmpp1[kkk1]=lmx;
	if(rmn>=0)tmp2[++kkk2]=rdis,tmpp2[kkk2]=rmx;
	go(u)if(!vis[v]&&v!=fa)dfs(v,u,ldis+a[v],rdis-a[v],max(lmx+a[v],a[v]),max(rmx,-rdis+a[v]),min(lmn+a[v],0ll),min(rmn-a[v],0ll));
}
void calc(ll u){
	kkk1=0;kkk2=0;
	vector<ll>son;
	go(u)if(!vis[v]){
		son.push_back(v);
		ll lst1=kkk1,lst2=kkk2;
		dfs(v,0,a[v],-a[u]-a[v],a[v],max(max(a[u],a[u]+a[v]),0ll),min(a[v],0ll),min(-a[u]-a[v],0ll));
		rep(j,lst2+1,kkk2)if(viss[tmp2[j]])ans=max(ans,max(bl[tmp2[j]],tmp2[j]+tmpp2[j]));
		rep(j,lst1+1,kkk1)bl[tmp1[j]]=max(bl[tmp1[j]],tmpp1[j]),viss[tmp1[j]]=1;
	}
	if(a[u]==-1)ans=max(ans,bl[1]);
	else rep(i,1,kkk2)if(tmp2[i]==0)ans=max(ans,tmpp2[i]);
	rep(i,1,kkk1)bl[tmp1[i]]=0,viss[tmp1[i]]=0;
	kkk1=0;kkk2=0;
	for(ll i=son.size()-1;i>=0;i--){
		ll v=son[i];
		ll lst1=kkk1,lst2=kkk2;
		dfs(v,0,a[v],-a[u]-a[v],a[v],max(max(a[u],a[u]+a[v]),0ll),min(a[v],0ll),min(-a[u]-a[v],0ll));
		rep(j,lst2+1,kkk2)if(viss[tmp2[j]])ans=max(ans,max(bl[tmp2[j]],tmp2[j]+tmpp2[j]));
		rep(j,lst1+1,kkk1)bl[tmp1[j]]=max(bl[tmp1[j]],tmpp1[j]),viss[tmp1[j]]=1;
	}
	if(a[u]==-1)ans=max(ans,bl[1]);
	else rep(i,1,kkk2)if(tmp2[i]==0)ans=max(ans,tmpp2[i]);
	rep(i,1,kkk1)bl[tmp1[i]]=0,viss[tmp1[i]]=0;
}
void solve(ll u){
	vis[u]=1;calc(u);
	go(u)if(!vis[v]){
		szRT=inf;TRsz=sz[v];Grt(v,0);solve(RT);
	}
}
int main(){
	n=read();rep(i,2,n)x=read(),add(i,x),add(x,i);
	rep(i,1,n)a[i]=(get()=='('?1:-1);
	szRT=inf;TRsz=n;Grt(1,0);solve(RT);
	writeln(ans);
}

Hacks

祝大家做题调题愉快。