洛谷P2056Hide捉迷藏||洛谷P4115Qtree4||SP2666QTREE4QueryonatreeIV

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include cstdio
#include algorithm
#include set
using namespace std;
struct E
{
int to,nxt,d;
}e[];
int f1[],ne;
int ff[],n,sum,fx[],sz[];
int eu[],pos[],dpx[],dpx2[],st[][],log2x[],lft[];
int root;
bool fl[],vis[];
multiset int s[],s2[],s3;
//s[i]:i点管辖的连通块各个点到i点上层重心的距离
//s2[i]:i点的各个下层重心的s的最大值,**再加上一个0（i点到自身距离）
//s3:各个s2的前2大值之和
int getdis(int x,int y)
{
int l=pos[x],r=pos[y];if(l r) swap(l,r);
int k=log2x[r-l+],t=dpx[pos[st[l][k]]] dpx[pos[st[r-lft[k]+][k]]]?st[r-lft[k]+][k]:st[l][k];
return dpx2[pos[x]]+dpx2[pos[y]]-*dpx2[pos[t]];
}
void getroot(int u,int fa)
{
sz[u]=;fx[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to] e[k].to!=fa)
{
getroot(e[k].to,u);
sz[u]+=sz[e[k].to];
fx[u]=max(fx[u],sz[e[k].to]);
}
fx[u]=max(fx[u],sum-sz[u]);
if(fx[u] fx[root]) root=u;
}
void getsz(int u,int fa)
{
sz[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to] e[k].to!=fa)
{
getsz(e[k].to,u);
sz[u]+=sz[e[k].to];
}
}
void getdeep(int u,int fa)
{
s[root].insert(getdis(u,ff[root]));
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to] e[k].to!=fa)
getdeep(e[k].to,u);
}
char tmp[];
int getmax2(int p)
{
if(s2[p].size() ) return -0x3f3f3f3f;
multiset int ::reverse_iterator it=s2[p].rbegin();int ans=;
ans+=*it;++it;ans+=*it;
return ans;
}
void solve(int u)
{
vis[u]=;
s2[u].insert();
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
getsz(e[k].to,);sum=sz[e[k].to];
root=;getroot(e[k].to,);
ff[root]=u;getdeep(root,);
if(!s[root].empty()) s2[u].insert(*s[root].rbegin());
solve(root);
}
s3.insert(getmax2(u));
}
void dfs1(int u,int fa,int d,int d2)
{
eu[++eu[]]=u;pos[u]=eu[];dpx[eu[]]=d;dpx2[eu[]]=d2;
for(int k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
{
dfs1(e[k].to,u,d+,d2+e[k].d);
eu[++eu[]]=u;
dpx[eu[]]=d;
dpx2[eu[]]=d2;
}
}
//void debugxxxx(multiset int s)
//{
// for(auto i : s) printf("%d ",i);
// puts("test");
//}
void change(int u)
{
int now;
s3.erase(s3.find(getmax2(u)));
if(!fl[u]) s2[u].erase(s2[u].find());
for(now=u;ff[now];now=ff[now])
{
s3.erase(s3.find(getmax2(ff[now])));
if(!s[now].empty()) s2[ff[now]].erase(s2[ff[now]].find(*s[now].rbegin()));
if(!fl[u]) s[now].erase(s[now].find(getdis(u,ff[now])));
}
fl[u]^=;
if(!fl[u]) s2[u].insert();
s3.insert(getmax2(u));
for(now=u;ff[now];now=ff[now])
{
if(!fl[u]) s[now].insert(getdis(u,ff[now]));
if(!s[now].empty()) s2[ff[now]].insert(*s[now].rbegin());
s3.insert(getmax2(ff[now]));
}
}
int num;
int main()
{
lft[]=;
fx[]=0x3f3f3f3f;
int i,j,a,b,la=,q,t,c;
for(i=;i i++) lft[i]=(lft[i-] );
for(i=;i i++)
{
if(i =lft[la+]) ++la;
log2x[i]=la;
}
scanf("%d",
for(i=;i i++)
{
scanf("%d%d%d", a, b,
e[++ne].to=b;e[ne].nxt=f1[a];e[ne].d=c;f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];e[ne].d=c;f1[b]=ne;
}
dfs1(,,,);
for(i=;i =eu[];i++) st[i][]=eu[i];
for(j=;( j) =eu[];j++)
for(i=;i+lft[j]- =eu[];i++)
if(dpx[pos[st[i][j-]]] dpx[pos[st[i+lft[j-]][j-]]])
st[i][j]=st[i+lft[j-]][j-];
else
st[i][j]=st[i][j-];
sum=n;getroot(,);
solve(root);
scanf("%d",
num=n;
while(q--)
{
scanf("%s",tmp);
if(tmp[]=='A')
{
if(num==) printf("They have disappeared.\n");
else if(num==) printf("0\n");
else printf("%d\n",max(*s3.rbegin(),));
}
else if(tmp[]=='C')
{
scanf("%d",
if(fl[t]) num++;else num--;
change(t);
}
}
return ;
}