（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)));
}