https://www.luogu.org/problem/P2056
题解:来自https://blog.csdn.net/ccsu_cat/article/details/101036382
这代码是真的长,一码就是150行+
特殊之处在于这个题需要维护一个可删堆
#include<bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<ll,ll>
using namespace std;//head
const int maxn=4e5+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
namespace graph{
vector<int>g[maxn];
bool vis[maxn];
int all,sz[maxn],root,maxt,father[maxn];
int _deep[maxn],_dfn[maxn],_cnt;
int son[maxn];
int _lca[maxn][int(log(maxn)/log(2))+1];
int logn[maxn];
void add(int a,int b){
g[a].emplace_back(b);g[b].emplace_back(a);
}
int dfs_root(int now,int fa){
int cnt=1;
son[now]=0;
for(auto to:g[now])if(to!=fa&&!vis[to]){
int ch=dfs_root(to,now);
son[now]=max(son[now],ch);
cnt+=ch;
}
son[now]=max(son[now],all-cnt);
if(son[now]<son[root]) root=now;
return sz[now]=cnt;
}
void dfs_lca(int now,int fa){
_dfn[now]=++_cnt;
_lca[_cnt][0]=_deep[now]=_deep[fa]+1;
for(auto to:g[now]) {
if(to==fa) continue;
dfs_lca(to,now);
_lca[++_cnt][0]=_deep[now];
}
}
class node{public:
priority_queue<int> x,y;
inline void push(int a){x.push(a);}
inline void remove(int a){y.push(a);}
inline int top(){
while(y.size()&&x.top()==y.top())
x.pop(),y.pop();return x.top();
}
inline int size(){return x.size()-y.size();}
inline void pop(){
while(y.size()&&x.top()==y.top())
x.pop(),y.pop();
x.pop();
}
inline int sectop(){int a=top();pop();int b=top();push(a);return b;}
}ans0,b[maxn],c[maxn];
void cal_st(){
logn[0]=-1;
rep(i,1,2e5+10) logn[i]=logn[i>>1]+1;
rep(j,1,logn[_cnt])rep(i,1,_cnt-(1<<j)+1)
_lca[i][j]=min(_lca[i][j-1],_lca[i+(1<<(j-1))][j-1]);
}
int _dis(int a,int b){
a=_dfn[a],b=_dfn[b];
if(a>b) swap(a,b);
int len=logn[b-a+1];
return min(_lca[a][len],_lca[b-(1<<len)+1][len]);
}
int dis(int a,int b){
int res=_deep[a]+_deep[b]-2*_dis(a,b);
return res;
}
void dfs_cal(int now,int fa){
c[root].push(dis(now,father[root]));
for(auto to:g[now]){
if(to==fa||vis[to]) continue;
dfs_cal(to,now);
}
}
void pusha(int now){
if(b[now].size()>=2)
ans0.push(b[now].top()+b[now].sectop());
}
void dela(int now){
if(b[now].size()>=2)
ans0.remove(b[now].top()+b[now].sectop());
}
void dfs_dv(int now,int fa){
father[now]=fa;vis[now]=1;
b[now].push(0);
dfs_cal(now,0);
for(auto to:g[now]){
if(vis[to]) continue;
all=sz[to],root=0;
dfs_root(to,0);
int tmp=root;
dfs_dv(root,now);
b[now].push(c[tmp].top());
}
pusha(now);
}
void on(int pos){
dela(pos);
b[pos].remove(0);
pusha(pos);
for(int now=pos;father[now];now=father[now]){
dela(father[now]);
b[father[now]].remove(c[now].top());
c[now].remove(dis(pos,father[now]));
if(c[now].size()) b[father[now]].push(c[now].top());
pusha(father[now]);
}
}
void off(int pos){
dela(pos);
b[pos].push(0);
pusha(pos);
for(int now=pos;father[now];now=father[now]){
dela(father[now]);
if(c[now].size()) b[father[now]].remove(c[now].top());
c[now].push(dis(pos,father[now]));
b[father[now]].push(c[now].top());
pusha(father[now]);
}
}
void init(int n){
_cnt=0;
dfs_lca(1,0);
cal_st();
son[0]=n;
all=n;root=0;
dfs_root(1,0);
dfs_dv(root,0);
}
}
using namespace graph;
bool sw[maxn];
int main() {IO;
int a,b;
rep(i,1,maxn-5) logn[i]=logn[i>>1]+1;
cin>>n;
rep(i,2,n){
cin>>a>>b;
add(a,b);
}
init(n);
int cnt=n;
cin>>m;
while(m--){
string s;cin>>s;
if(s[0]=='G'){
if(cnt<=1) cout<<cnt-1<<endl;
else cout<<ans0.top()<<endl;
}else {
int pos;cin>>pos;
if(!sw[pos]) on(pos),--cnt;
else off(pos),++cnt;
sw[pos]^=1;
}
}
}