首先有一个东西叫做括号序列，即每一个点入栈加左括号，出栈加右括号
容易证明，括号序列中A到B的距离是A到B中消去所有成对出现后剩余括号的数量
用线段树来维护，考虑某个区间中两点的距离最大值，分为两种情况：1.点对在左区间/右区间；2.跨过区间的中点
前者很好处理，来分析一下后者：容易发现消去成对的括号后剩余括号一定是a个)和b个(，设左边的后缀状态是(a1,b1)，右边的前缀状态是(a2,b2)，那么合并起来长度就是a1+|b1-a2|+b2
这个东西仍然不好维护，将abs转化为max，即max(a1+b1+(b2-a2),(a1-b1)+a2+b2)，也就是维护：1.前/后缀最大距离（这个的计算方式类似于总答案的计算方式）；2.前缀最大右括号-左括号；3.后缀最大左括号-右括号即可（因为消去也是成对消去的，差值不变）
同时为了维护这些东西，还需要维护整个区间消去括号后左/右括号的数量即可，具体实现可能比较复杂，要注意初始状态和合并，可以参考代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define L (k<<1)
 5 #define R (L+1)
 6 #define mid (l+r>>1)
 7 #define inf 0x3f3f3f3f
 8 struct ji{
 9     int nex,to;
10 }edge[N<<1];
11 struct node{
12     int ll,rl,lm,rm,ls,rs,ans;
13 }f[N<<4];
14 int E,n,m,x,y,head[N],p[N],id[N],a[N<<2];
15 char s[11];
16 void add(int x,int y){
17     edge[E].nex=head[x];
18     edge[E].to=y;
19     head[x]=E++;
20 }
21 void dfs(int k,int fa){
22     a[++x]=-1;
23     a[++x]=k;
24     id[k]=x;
25     for(int i=head[k];i!=-1;i=edge[i].nex)
26         if (edge[i].to!=fa)dfs(edge[i].to,k);
27     a[++x]=-2;
28 }
29 void init(int k,int l){
30     f[k]=node{0,0,-inf,-inf,-inf,-inf,-inf};
31     if (!a[l])return;
32     if (a[l]>0)f[k]=node{0,0,0,0,0,0,-inf};
33     else
34         if (a[l]==-1)f[k].rl=1;
35         else f[k].ll=1;
36 }
37 void up(int k){
38     f[k].ll=f[L].ll+max(f[R].ll-f[L].rl,0);
39     f[k].rl=f[R].rl+max(f[L].rl-f[R].ll,0);
40     f[k].lm=max(f[L].lm,f[L].rl-f[L].ll+f[R].lm);
41     f[k].rm=max(f[R].rm,f[R].ll-f[R].rl+f[L].rm);
42     f[k].ls=max(f[L].ls,max(f[L].ll-f[L].rl+f[R].ls,f[L].ll+f[L].rl+f[R].lm));
43     f[k].rs=max(f[R].rs,max(f[L].rs+f[R].rl-f[R].ll,f[L].rm+f[R].ll+f[R].rl));
44     f[k].ans=max(max(f[L].ans,f[R].ans),max(f[L].rs+f[R].lm,f[L].rm+f[R].ls));
45 }
46 void build(int k,int l,int r){
47     if (l==r){
48         init(k,l);
49         return;
50     }
51     build(L,l,mid);
52     build(R,mid+1,r);
53     up(k);
54 }
55 void update(int k,int l,int r,int x){
56     if (l==r){
57         init(k,l);
58         return;
59     }
60     if (x<=mid)update(L,l,mid,x);
61     else update(R,mid+1,r,x);
62     up(k);
63 }
64 int main(){
65     scanf("%d",&n);
66     memset(head,-1,sizeof(head));
67     for(int i=1;i<n;i++){
68         scanf("%d%d",&x,&y);
69         add(x,y);
70         add(y,x);
71     }
72     x=0;
73     dfs(1,0);
74     build(1,1,3*n);
75     scanf("%d",&m);
76     for(int i=1;i<=m;i++){
77         scanf("%s",s);
78         if (s[0]=='G')
79             if (f[1].ans<0)printf("-1\n");
80             else printf("%d\n",f[1].ans);
81         else{
82             scanf("%d",&x);
83             a[id[x]]^=x;
84             update(1,1,3*n,id[x]);
85         }
86     }
87 }

View Code