```cpp
#include<bits/stdc++.h>
#define rd(x) x=read()
#define R register
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
inline int read(){int x=0,f=1;char ch=getchar();while((ch>'9' || ch<'0')){if(ch=='-') f=-1;ch=getchar();}while('0'<=ch && ch<='9') x=x*10+(ch^48),ch=getchar();return x*f;}
int n,m,x,y,Q,CNT;
vector<int> T[N];
inline void add(int u,int v) {T[u].push_back(v);T[v].push_back(u);}
struct heap
{
priority_queue<int> inse,dele;
inline int size(){return inse.size()-dele.size();}
inline int ins(int x){inse.push(x);}
inline int del(int x){dele.push(x);}
inline int MAX() {while (!inse.empty() && !dele.empty() && inse.top()==dele.top()) {dele.pop();inse.pop();}return inse.top();}
inline int SEC() {int Max=MAX();inse.pop();int ret=MAX();inse.push(Max);return ret;}
}stf[N],fts[N],all;//son to fa | fa to son | all
inline void del(int u) {if (fts[u].size()>=2) all.del(fts[u].MAX()+fts[u].SEC());}
inline void ins(int u) {if (fts[u].size()>=2) all.ins(fts[u].MAX()+fts[u].SEC());}
int SIZ/*整棵子树的大小*/,G;
int siz[N],son[N];
bool vis[N];
inline void getG(int u,int fa)
{
siz[u]=1,son[u]=0;
for (R int i=0;i<T[u].size();i++)
{
int v=T[u][i];if (v==fa || vis[v]) continue;
getG(v,u);
siz[u]+=siz[v];son[u]=max(son[u],siz[v]);
}
son[u]=max(son[u],SIZ-son[u]);
if (son[u]<son[G]) G=u;
}
int dep[N],Fa[N],col[N];
inline void getdis(int u,int fa,int st,int rt)
{
stf[rt].ins(st);
for (R int i=0;i<T[u].size();i++)
{
int v=T[u][i];if (v==fa || vis[v]) continue;
getdis(v,u,st+1,rt);
}
}
inline void solve(int u)
{
vis[u]=1;
for (R int i=0;i<T[u].size();i++)
{
int v=T[u][i];if (vis[v]) continue;
G=0;son[0]=inf;SIZ=siz[v];
getG(v,u);Fa[G]=u;
getdis(v,u,1,G);
fts[u].ins(stf[G].MAX());
solve(G);
}
fts[u].ins(0);ins(u);
}
int anc[N][25];
inline void init(int u,int fa)
{
dep[u]=dep[fa]+1;
anc[u][0]=fa;
for (R short i=1;i<=17;i++) anc[u][i]=anc[anc[u][i-1]][i-1];
for (R int i=0;i<T[u].size();i++) if (T[u][i]!=fa) init(T[u][i],u);
}
inline int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (R short i=17;i>=0;i--) if (dep[x]-(1<<i)>=dep[y]) x=anc[x][i];
if (x==y) return x;
for (R short i=17;i>=0;i--) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
inline int realdis(int x,int y){return dep[x]+dep[y]-dep[lca(x,y)]*2;}
inline void update(int u)
{
int opt=col[u];
del(u);if (opt==0) fts[u].del(0);else fts[u].ins(0);
ins(u);
for (R int v=u;Fa[v];v=Fa[v])
{
int D=realdis(u,Fa[v]);
del(Fa[v]);
if (stf[v].size()) fts[Fa[v]].del(stf[v].MAX());
if (opt==0) stf[v].del(D);else stf[v].ins(D);
if (stf[v].size()) fts[Fa[v]].ins(stf[v].MAX());
ins(Fa[v]);
}
}
int main()
{
rd(n);
for (R int i=1;i<n;i++) {rd(x);rd(y);add(x,y);}init(1,0);
G=0;son[0]=SIZ=n;
getG(1,0);solve(G);CNT=n;
rd(Q);
while (Q--)
{
char ch=getchar();
if (ch=='G'){if (CNT==0)puts("-1");else if(CNT==1)puts("0");else printf("%d\n",all.MAX());}
else {int num=read();if (col[num]==1) CNT++;else CNT--;update(num);col[num]^=1;}
}
}
```
by AsunderSquall @ 2020-11-27 18:54:08
- 码风很阴间,不要在意
- 或者谁能告诉我为什么这段代码厌氧啊
by AsunderSquall @ 2020-11-27 18:54:49
数据$1e5$,理论上两只log的dfs是能过的
by AsunderSquall @ 2020-11-27 18:55:19
dfs=点分树?
by DPair @ 2020-11-27 18:56:27
不需要理解代码,帮忙卡常就行了qwq
by AsunderSquall @ 2020-11-27 18:56:41
艹你卡常还敢用倍增LCA
by tommy0221 @ 2020-11-27 18:56:51
或者谁能给个下载数据的通道?
by AsunderSquall @ 2020-11-27 18:57:00
@[世外明月](/user/123384) 有道理,我等下再来
by AsunderSquall @ 2020-11-27 18:57:19
草,你点分树跟着什么东西学的啊,点分树常数巨大无比,求LCA必用RMQ LCA啊
by 火车司机 @ 2020-11-27 19:03:54
点分树寻找子树内的分治中心时一般要重新求一遍 siz 数组的大小,你这种写法的复杂度是错的,等一下我找一下参考资料给你
by 火车司机 @ 2020-11-27 19:06:28