题目链接
这题原来一直T,题解也大多是点分治括号序列等。
我是用边分治写的。
加上快读和O2,这题就过了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
return re;
}
inline char read_charA()
{
char c;
for(c=Get_Char();c<'A'||c>'Z';c=Get_Char());
return c;
}
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=200100;
int head[maxn],ver[maxn*20],edge[maxn*20],nt[maxn*20];
int Head[maxn],Ver[maxn<<1],Edge[maxn<<1],Nt[maxn<<1],tail[maxn],pre[maxn*20];
int d[maxn];
bool ha[maxn];
int nown,n,tot,TOT,root,midedge,maxx,cnt;
void init(void)
{
memset(head,0,sizeof(head));
tot=1;
}
void Init(void)
{
memset(Head,0,sizeof(Head));
TOT=1;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void Add(int x,int y,int z)
{
Ver[++TOT]=y,Edge[TOT]=z;
Nt[TOT]=Head[x],Head[x]=TOT;
}
void get_pre(void)
{
memset(tail,0,sizeof(tail));
for(int x=1;x<=nown;x++)
{
for(int i=Head[x];i;i=Nt[i])
{
pre[i]=tail[x];
tail[x]=i;
}
}
}
void del(int x,int i)
{
if(Head[x]==i) Head[x]=Nt[i];
else Nt[pre[i]]=Nt[i];
if(tail[x]==i) tail[x]=pre[i];
else pre[Nt[i]]=pre[i];
}
void build(int x,int fa)
{
int now=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(y==fa) continue;
if(!now)
{
Add(x,y,z),Add(y,x,z);
now=x;
}
else
{
ha[++nown]=false;
Add(nown,now,0),Add(now,nown,0);
Add(y,nown,z),Add(nown,y,z);
now=nown;
}
build(y,x);
}
}
void rebuild(void)
{
Init();
nown=n;
for(int i=1;i<=nown;i++) ha[i]=1;
build(1,0);
get_pre();
init();
}
struct point
{
int y;
int dis;
point(){}
point(int a,int b)
{
y=a,dis=b;
}
friend bool operator <(const point &a,const point &b)
{
return a.dis<b.dis;
}
};
struct node
{
int root,midlen,ans;
int lson,rson;
priority_queue<point>q;
}t[maxn<<1];
void _init(void)
{
for(int i=1;i<maxn<<2;i++)
{
while(t[i].q.size())
t[i].q.pop();
t[i].lson=t[i].rson=0;
}
cnt=1;
}
void dfs_size(int x,int fa,int dis)
{
add(x,root,dis);
if(ha[x]) t[root].q.push(point(x,dis));
d[x]=1;
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i],z=Edge[i];
if(y==fa) continue;
dfs_size(y,x,dis+z);
d[x]+=d[y];
}
}
void dfs_midedge(int x,int nowi)
{
if(max(d[x],d[t[root].root]-d[x])<maxx)
{
maxx=max(d[x],d[t[root].root]-d[x]);
midedge=nowi;
}
for(int i=Head[x];i;i=Nt[i])
{
int y=Ver[i];
if(i!=(nowi^1)) dfs_midedge(y,i);
}
}
void pushup(int id)
{
t[id].ans=-1;
while(t[id].q.size()&&ha[t[id].q.top().y]==0) t[id].q.pop();
int lson=t[id].lson,rson=t[id].rson;
if(lson==0&&rson==0)
{
if(ha[t[id].root]) t[id].ans=0;
}
else
{
if(t[lson].ans>t[id].ans) t[id].ans=t[lson].ans;
if(t[rson].ans>t[id].ans) t[id].ans=t[rson].ans;
if(t[lson].q.size()&&t[rson].q.size())
t[id].ans=max(t[id].ans,t[lson].q.top().dis+t[rson].q.top().dis+t[id].midlen);
}
}
void dfs(int id,int x)
{
root=id,maxx=nown,midedge=0;
t[id].root=x;
dfs_size(x,0,0);
dfs_midedge(x,0);
if(midedge)
{
int p1=Ver[midedge];
int p2=Ver[midedge^1];
t[id].midlen=Edge[midedge];
t[id].lson=++cnt;
t[id].rson=++cnt;
del(p1,midedge^1);
del(p2,midedge);
dfs(t[id].lson,p1);
dfs(t[id].rson,p2);
}
pushup(id);
}
void update(int x)
{
ha[x]^=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(ha[x]==1) t[y].q.push(point(x,z));
pushup(y);
}
}
int main(void)
{
n=read();
init();
cnt=1;
int x,y;
for(int i=1;i<n;i++)
{
x=read(),y=read();
add(x,y,1);
add(y,x,1);
}
rebuild();
dfs(1,1);
int m,pos;
char str;
m=read();
for(int i=1;i<=m;i++)
{
str=read_charA();
if(str=='G')
{
if(t[1].ans==-1) printf("They have disappeared.\n");
else printf("%d\n",t[1].ans);
}
else
{
pos=read();
update(pos);
}
}
return 0;
}