题目链接:
题解:
样例好良心,调样例3h一A……
细节好多……诸如没完没了的pop和push……搞得头都大了。
同情zzh……调了整一天了。
动态点分治裸题……果然每个“裸题”打起来都跟shi一样。
题目:
#define Troy
#define inf 0x7fffffff #include <bits/stdc++.h> using namespace std; inline int read(){
int s=,k=;char ch=getchar();
while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while(ch>&ch<='') s=s*+(ch^),ch=getchar();
return k*s;
} const int N=1e5+; struct edges{
int v;edges *last;
}edge[N<<],*head[N];int cnt; inline void push(int u,int v){
edge[++cnt]=(edges){v,head[u]};head[u]=edge+cnt;
} int n,m,f[N][],deep[N],bit[]; inline void dfs(int x){
for(int i=;bit[i]<=deep[x];++i)
f[x][i]=f[f[x][i-]][i-];
for(edges *i=head[x];i;i=i->last) if(i->v!=f[x][]){
deep[i->v]=deep[x]+;
f[i->v][]=x;
dfs(i->v);
}
} inline int lca(int x,int y){
int ret=deep[x]+deep[y];
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=;t;++i)
if(bit[i]&t) t^=bit[i],x=f[x][i];
if(x!=y){
for(int i=;~i;--i)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
x=f[x][];
}
return ret-(deep[x]<<);
} priority_queue<int,vector<int>,less<int> > q[N][],e[N][],ans,anse;
int size[N],heavy[N],top,tot,root,lastans[N],lasttop[N],fat[N];
bool vis[N]; inline void dfs(int x,int fa){
size[x]=;
heavy[x]=;
for(edges *i=head[x];i;i=i->last) if(!vis[i->v]&&i->v!=fa){
dfs(i->v,x);
size[x]+=size[i->v];
heavy[x]=max(heavy[x],size[i->v]);
}heavy[x]=max(heavy[x],tot-size[x]);
if(heavy[x]<top) top=heavy[x],root=x;
} inline void build(int x,int fa,int grand){
q[grand][].push(lca(x,fat[grand]));
size[x]=;
for(edges *i=head[x];i;i=i->last) if(!vis[i->v]&&i->v!=fa)
build(i->v,x,grand),size[x]+=size[i->v];
} inline void build(int x,int fa){
top=inf;
dfs(x,x);
vis[x=root]=true;
dfs(x,x);
fat[x]=fa;
build(x,x,x);
for(edges *i=head[x];i;i=i->last)if(vis[i->v]^){
tot=size[i->v];
build(i->v,x);
if(q[root][].empty()^)
q[x][].push(lasttop[root]=q[root][].top());
}
if(!q[x][].empty()){
int a1=q[x][].top();
q[x][].pop();
ans.push(lastans[x]=a1+(q[x][].empty()?:q[x][].top()));
q[x][].push(a1);
}
root=x;
} inline void putans(){
while(!ans.empty()&&!anse.empty()){
if(ans.top()==anse.top())
ans.pop(),anse.pop();
else break;
}
if(tot<=){
printf("%d\n",tot-);
}else
printf("%d\n",ans.top());
} inline void clear(int x,bool k){
while(!q[x][k].empty()&&!e[x][k].empty()&&q[x][k].top()==e[x][k].top())
q[x][k].pop(),e[x][k].pop();
} inline void erase(int x,int s,int er){
int now=-;
if(fat[x]){
if(vis[er])
e[x][].push(lca(er,fat[x]));
else
q[x][].push(lca(er,fat[x]));
clear(x,);
erase(fat[x],x,er);
}
if(s) {
if(q[s][].empty()^)
now=q[s][].top();
if(lasttop[s]!=now){
if(lasttop[s]!=-)
e[x][].push(lasttop[s]);
if(now!=-)
q[x][].push(now);
}else return;
lasttop[s]=now;
}
clear(x,);
now=-;
if(q[x][].empty()^){
int a1=q[x][].top();
q[x][].pop();
clear(x,);
if(q[x][].empty()^)
now=a1+q[x][].top();
else if(!vis[x]) now=a1;
q[x][].push(a1);
}
if(lastans[x]!=now){
if(lastans[x]!=-)
anse.push(lastans[x]);
if(now!=-)
ans.push(now);
}lastans[x]=now;
} inline void update(int x){
vis[x]^=;
if(vis[x]) --tot;
else ++tot;
erase(x,,x);
} int main(){
n=read();
register int i;
for(i=;i^n;++i){
int a=read(),b=read();
push(a,b),push(b,a);
}
for(i=;i^;++i) bit[i]=<<i;
memset(lastans,-,sizeof(lastans));
memset(lasttop,-,sizeof(lasttop));
dfs();tot=n;
build(,);
memset(vis,,sizeof(vis));
tot=n;
m=read();
while(m--){
char opt[];
scanf("%s",opt);
if(opt[]=='G') putans();
else update(read());
}
}