CF1149C 题解

（Link，Div1，2700）

首先把边上的括号序转换成不完整的点上括号序：把每条边上的括号下放到它所指向的儿子处，题设序列就变成了“从根节点开始遍历整棵树，除根结点外，每开始访问和结束访问某个结点的子树时分别将一个 ( 和一个 ) 添加至序列末尾”所最终形成的括号序。借鉴树上莫队的方式方法可知这个括号序的子串们 去掉匹配括号后的长度（以下简称“去匹长”）可以满射到树上任意一条路径的长度，且它们相等（实际上是子串去掉匹配括号后可以直接满射到路径上，感性理解）：

/[/forall u/in[1,n]/land v/in[1,n]/land u/le v,/exist i/in[1,2n-2]/land j/in [1,2n-2]/land i/le j,f((i,j))=(u,v)
/]

其中 /(f/) 是一种奇怪的映射，具体可以访问这篇blog中的【树上莫队】篇内容。

于是树的直径变成了【子串们去匹长的最大值】。这东西很难看，考虑具象化，赋予每个 ( /(1/) 的权值以及每个 ) /(-1/) 的权值，一个串的去匹长转化为把这个串分成两段（均可以为空）后 后面一段的权值和减去前面一段的权值和 的最大值：

/[/operatorname{len/_extract/_match}(t)=/max_{i=0}^{|t|} /left(/sum_{j=i+1}^{|t|} val(t_j)/right)-/left(/sum_{j=1}^i val(t_j)/right)
/]

这个仍然可以感性理解，分出来的后面那段要放尽量多的 ( 也就是权值尽量大，前面那段要放尽量多的 ) 也就是权值尽量小，加减的过程中匹配的 ( 和 ) 会被自动消掉。

外面再套上一层 /(/max/)，求出一个串 /(S/) 的任意一个子串 /(t/) 去匹长的最大值：

/[/operatorname{max/_substr/_len/_extract/_match}(S)=/max_{t/in substr(S)} /max_{i=0}^{|t|} /left(/sum_{j=i+1}^{|t|} val(t_j)/right)-/left(/sum_{j=1}^i val(t_j)/right)//
=/max_{i=0}^{|S|} /left(/sum_{j=i+1}^{|S|} val(S_j)/right)-/left(/sum_{j=1}^i val(S_j)/right)
/]

做到这一步题目中 swap 已经没有任何性质了，线段树维护然后模拟之即可。

重头戏来了。每个结点需要维护 /(7/) 个值（设其维护的区间为 /([l,r]/)）：

• ans，该结点答案，即 /([l,r]/) 这个子串的所有子串们去匹长的最大值；
• whans，用上 /([l,r]/) 这个子串的所有位置组成串的去匹长，也就是 /([l,r]/) 这个子串的去匹长；
• lans，包含 /(l/) 这个位置的 /([l,r]/) 的子串的去匹长的最大值，即前缀最大去匹长；
• rans，包含 /(r/) 这个位置的 /([l,r]/) 的子串的去匹长的最大值，即后缀最大去匹长；
• sum，/([l,r]/) 的权值和；
• lmx，/([l,r]/) 中包含 /(l/) 这个位置的 /([l,r]/) 的子串的权值和最大值，即前缀最大权值和；
• rmx，/([l,r]/) 中包含 /(r/) 这个位置的 /([l,r]/) 的子串的权值和最大值，即后缀最大权值和。

剩下的就是如何 pushup 了，十分的简单，简单到笔者在赛时AC本题的 dalao 的帮助下调了6h：

void updata(int x){
    ans(x)=max(max(ans(ls(x)),ans(rs(x))),
               max(lans(rs(x))-min(rmn(ls(x)),0),rans(ls(x))+max(lmx(rs(x)),0)));
    whans(x)=max(whans(ls(x))+sum(rs(x)),whans(rs(x))-sum(ls(x)));
    lans(x)=max(lans(ls(x)),max(whans(ls(x))+max(lmx(rs(x)),0),lans(rs(x))-sum(ls(x))));
    rans(x)=max(rans(rs(x)),max(whans(rs(x))-min(rmn(ls(x)),0),rans(ls(x))+sum(rs(x))));
    sum(x)=sum(ls(x))+sum(rs(x));
    lmx(x)=max(lmx(ls(x)),sum(ls(x))+lmx(rs(x)));
    rmn(x)=min(rmn(rs(x)),sum(rs(x))+rmn(ls(x)));
}