【题解】P3060 Balanced Trees G

· · 题解

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

是一道板子+细节题，如果想要调试的可以去最下方获得 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

祝大家做题调题愉快。