动态树分治，用三个set分别维护每个重心到每一个子树的距离种类、每个重心所有子树的最大值和次大值、全局答案的最大值。复杂度O(nlogn^2)
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define pb push_back
using namespace std;
const int N = ;
int size[N],flag[N],n,a,b,i,f[N],cnt,typ[N],deep[N];
int jump[N][];
int q;
char ch[];
vector<int> e[N];
multiset<int> dist[N],ans[N],Ans;
multiset<int>::iterator it;
int getroot(int x,int fa,int n)
{
int i,tmp=,rt=;
size[x]=;
for (i=;i<e[x].size();i++)
if ((e[x][i]!=fa)&&(!flag[e[x][i]]))
{
rt|=getroot(e[x][i],x,n);
size[x]+=size[e[x][i]];
if (size[e[x][i]]>n/) tmp=;
}
if (n-size[x]>n/) tmp=;
if (tmp==) return rt;else return x;
}
void gao(int x,int fa,int y,int dis)
{
dis++;
int i;
dist[y].insert(dis);
for (i=;i<e[x].size();i++)
if ((!flag[e[x][i]])&&(e[x][i]!=fa))
gao(e[x][i],x,y,dis);
}
void DFS(int x,int fa)
{
int i;
deep[x]=deep[fa]+;
jump[x][]=fa;
for (i=;i<=;i++)
jump[x][i]=jump[jump[x][i-]][i-];
for (i=;i<e[x].size();i++)
if (e[x][i]!=fa) DFS(e[x][i],x);
}
int lca(int a,int b)
{
int i;
if (deep[a]<deep[b]) a^=b^=a^=b;
for (i=;i>=;i--)
if (deep[jump[a][i]]>=deep[b]) a=jump[a][i];
if (a==b) return a;
for (i=;i>=;i--)
if (jump[a][i]!=jump[b][i]) a=jump[a][i],b=jump[b][i];
return jump[a][];
}
int getdis(int x,int y)
{
int z=lca(x,y);
return deep[x]+deep[y]-*deep[z];
}
void del(int x)
{
int tmp=;
if (ans[x].size()>=)
{
it=ans[x].end();
--it;tmp+=*it;
--it;tmp+=*it;
it=Ans.lower_bound(tmp);
Ans.erase(it);
}
}
void ins(int x)
{
int tmp=;
if (ans[x].size()>=)
{
it=ans[x].end();
--it;tmp+=*it;
--it;tmp+=*it;
Ans.insert(tmp);
}
}
void DEL(int y)
{
if (dist[y].size())
{
it=dist[y].end();--it;
int tmp=*it;
it=ans[f[y]].lower_bound(tmp);
ans[f[y]].erase(it);
}
}
void INS(int y)
{
if (dist[y].size())
{
it=dist[y].end();--it;
int tmp=*it;
ans[f[y]].insert(tmp);
}
}
int change(int x,int y)
{
del(x);
if (typ[x]==)
{
it=ans[x].lower_bound();
ans[x].erase(it);
}
else
ans[x].insert();
while (x)
{
ins(x);
if (f[x])
{
del(f[x]);
DEL(x);
int dis=getdis(f[x],y);
if (typ[y]==)
{
it=dist[x].lower_bound(dis);
dist[x].erase(it);
}
else
dist[x].insert(dis);
INS(x);
}
x=f[x];
}
}
int dfs(int x,int n,int fa)
{
int i,y;
x=getroot(x,,n);
f[x]=fa;
flag[x]=;
ans[x].insert();
for (i=;i<e[x].size();i++)
if (!flag[e[x][i]])
{
if (size[e[x][i]]>size[x])
y=dfs(e[x][i],n-size[x],x);
else
y=dfs(e[x][i],size[e[x][i]],x);
gao(e[x][i],,y,);
it=dist[y].end();
ans[x].insert(*(--it));
}
ins(x);
flag[x]=;
return x;
}
int main()
{
scanf("%d",&n);
for (i=;i<n;i++)
{
scanf("%d%d",&a,&b);
e[a].pb(b);
e[b].pb(a);
}
dfs(,n,);
DFS(,);
scanf("%d",&q);
for (i=;i<=q;i++)
{
scanf("%s",ch+);
if (ch[]=='G')
{
if (cnt==n)
printf("-1\n");
else
if (cnt==n-)
printf("0\n");
else
{
it=Ans.end();--it;
printf("%d\n",*it);
}
}
else
if (ch[]=='C')
{
scanf("%d",&a);
if (typ[a]==)
cnt++,typ[a]=;
else
cnt--,typ[a]=;
change(a,a);
}
}
}