文章目录

可以将欧拉序转化为括号序列。
访问一个点时加一个左括号,再把这个点放这,离开时放一个右括号。
显然任意两点间的距离即为括号序列中将它们之间可匹配的括号全部去掉后剩下的括号的数量。
可以使用线段树来维护。
以下为将可以匹配括号删除的情况:
c1,c2代表多余的左括号和右括号
l2所有黑点到左端点左括号与右括号的数量的差值的最大值
r2所有黑点到右端点右括号与左括号的数量的差值的最大值
l1所有黑点到左端点的括号数量的最大值
r1所有黑点到右端点的括号数量的最大值
dis代表最大答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<algorithm>
#include<cstdio>
#define ll int
#define inf 1000000000
#define maxn 100010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
char s[10];
ll n,q,cnt,tot,sum;
ll head[maxn],v[maxn*3],next[maxn*2],vet[maxn*2],pos[maxn],c[maxn];
struct data{
ll l1,r1,l2,r2,dis,c1,c2;
void New(ll x){
dis=-inf; c1=c2=0;
if (v[x]==-6) c2=1;
if (v[x]==-9) c1=1;
if (v[x]>0&&c[v[x]]) l1=r1=l2=r2=0;
else l1=r1=l2=r2=-inf;
};
}tr[maxn*12];
data merge(data x,data y){
data s;
ll a=x.c1,b=x.c2,c=y.c1,d=y.c2;
s.dis=max(max(x.dis,y.dis),max(x.r1+y.l2,x.r2+y.l1));
s.r1=max(y.r1,max(x.r1-c+d,x.r2+c+d));
s.l1=max(x.l1,max(y.l1-b+a,y.l2+b+a));
s.r2=max(y.r2,x.r2+c-d);
s.l2=max(x.l2,y.l2+b-a);
if (b<c) s.c1=a-b+c,s.c2=d;
else s.c1=a,s.c2=b-c+d;
return s;
}
void insert(ll x,ll y){
next[++cnt]=head[x]; head[x]=cnt; vet[cnt]=y;
}
void dfs(ll x,ll pre){
v[++tot]=-6; v[++tot]=x; pos[x]=tot;
for(ll i=head[x];i;i=next[i])
if (vet[i]!=pre) dfs(vet[i],x);
v[++tot]=-9;
}
void build(ll p,ll l,ll r){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
void modify(ll p,ll l,ll r,ll x){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
if (x<=mid) modify(p<<1,l,mid,x);
else modify(p<<1|1,mid+1,r,x);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
int main(){
sum=n=read();
For(i,1,n) c[i]=1;
For(i,1,n-1){
ll x=read(),y=read();
insert(x,y); insert(y,x);
}
dfs(1,-1); build(1,1,tot);
q=read();
while(q--){
scanf("%s",s);
if (s[0]=='C'){
ll x=read();
sum-=c[x]?1:-1;
c[x]^=1;
modify(1,1,tot,pos[x]);
}else{
if (!sum) puts("-1");
else if (sum==1) puts("0");
else writeln(tr[1].dis);
}
}
}

文章目录