description
solution
动态点分治第一题。
本来是想写[ZJOI2015]幻想乡战略游戏来着
动态维护最远点对
考虑每次暴力点分治的过程，相当于对于所有过重心的路径判一个最大值
于是我们在动态点分治的时候，对于每一个节点开一个堆，修改的时候往父亲维护即可
重写了至少3遍
果然我还是太弱了导致全方位被暴踩
code
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e9+7;
const int N=100010;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n;
int head[N],nxt[N<<1],to[N<<1],cnt;
il void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
/*********************************************************************/
int siz[N],dep[N],son[N],pa[N],top[N];
void dfs1(int u,int ff){
siz[u]=1;pa[u]=ff;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff)continue;
dep[v]=dep[u]+1;dfs1(v,u);siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==pa[u]||v==son[u])continue;
dfs2(v,v);
}
}
il int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=pa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
il int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
/*********************************************************************/
struct heap{
priority_queue<int>q,d;
il void push(int u){q.push(u);}
il int size(){return q.size()-d.size();}
il void pop(){
while(!d.empty()&&d.top()==q.top())d.pop(),q.pop();
q.pop();
}
il void del(int u){d.push(u);}
il int top(){
while(!d.empty()&&d.top()==q.top())d.pop(),q.pop();
if(q.empty())return -inf;return q.top();
}
il int s_top(){
if(size()<2)return -inf;
int x=top();pop();int y=top();push(x);return y;
}
}A[N],B[N],C;
/*********************************************************************/
int rt,sum,sz[N],fa[N],w[N];bool vis[N];
void getrt(int u,int ff){
sz[u]=1;w[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
getrt(v,u);sz[u]+=sz[v];
w[u]=max(w[u],sz[v]);
}
w[u]=max(w[u],sum-sz[u]);
if(w[rt]>w[u])rt=u;
}
void solve(int u,int ff){
vis[u]=1;fa[u]=ff;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
sum=sz[v];rt=0;
getrt(v,0);
solve(rt,u);
}
}
/*********************************************************************/
bool bw[N];int tot;
il void modify(int u){
bw[u]^=1;tot+=bw[u];
if(bw[u]){
B[u].push(0);if(B[u].size()==2)C.push(B[u].top());
for(RG int x=u;fa[x];x=fa[x]){
RG int ff=fa[x],D=dist(u,ff),tmp=A[x].top();
A[x].push(D);
if(tmp<0||D>tmp){
RG int mx=B[ff].top()+B[ff].s_top();
if(tmp>=0)B[ff].del(tmp);
B[ff].push(D);
RG int nw=B[ff].top()+B[ff].s_top();
if(mx<0||nw>mx){
if(mx>=0)C.del(mx);
if(nw>=0)C.push(nw);
}
}
}
}
else{
if(B[u].size()==2)C.del(B[u].top());B[u].del(0);
for(RG int x=u;fa[x];x=fa[x]){
RG int ff=fa[x],D=dist(u,ff),tmp=A[x].top();
A[x].del(D);
if(tmp==D){
RG int mx=B[ff].top()+B[ff].s_top();
B[ff].del(tmp);
if(A[x].top()>=0)B[ff].push(A[x].top());
RG int nw=B[ff].top()+B[ff].s_top();
if(nw<0||nw<mx){
if(mx>=0)C.del(mx);
if(nw>=0)C.push(nw);
}
}
}
}
}
int Q;
il int query(){
if(tot<=1)return tot-1;
return C.top();
}
/*********************************************************************/
int main()
{
n=read();
for(RG int i=1,u,v;i<n;i++){
u=read();v=read();add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,1);
sum=w[0]=n;rt=0;
getrt(1,0);
solve(rt,0);
for(RG int i=1;i<=n;i++)modify(i);
Q=read();
for(RG int i=1,c;i<=Q;i++){
c=0;while(c!='C'&&c!='G')c=getchar();
if(c=='C')modify(read());
else printf("%d
",query());
}
return 0;
}