| 记录编号 |
549078 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[ZJOI 2007]捉迷藏 |
最终得分 |
100 |
| 用户昵称 |
 瑆の時間~無盡輪迴·林蔭 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
7.503 s |
| 提交时间 |
2020-02-06 03:07:43 |
内存使用 |
36.74 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<ctime>
#include<set>
#include<vector>
#include<queue>
using namespace std;
#define inf 0x3fffffff
#define Vt Vater[rt]
#define N 100010
int n,e;
vector<int> s[N];
int Vater[N],size[N],root,totsize,maxs[N];
bool state[N],vis[N];
struct heap
{
priority_queue<int>q1,q2;
inline void push(int x)
{
q1.push(x);
}
inline void erase(int x)
{
q2.push(x);
}
inline int top()
{
while(q2.size()&&q1.top()==q2.top())
{
q1.pop();
q2.pop();
}
return q1.top();
}
inline void pop()
{
while(q2.size()&&(q1.top()==q2.top()))
{
q1.pop();
q2.pop();
}
q1.pop();
}
inline int top2()
{
int val=top();
pop();
int ret=top();
push(val);
return ret;
}
inline int size()
{
return q1.size()-q2.size();
}
};
heap h1[N],h2[N],h3;
inline void DFS1(int rt,int fa)
{
size[rt]=1;
maxs[rt]=0;
for(int i=0;i<s[rt].size();i++)
{
int to=s[rt][i];
if(to!=fa&&!vis[to])
{
DFS1(to,rt);
size[rt]+=size[to];
maxs[rt]=max(maxs[rt],size[to]);
}
}
maxs[rt]=max(maxs[rt],totsize-maxs[rt]);
if(maxs[rt]<maxs[root])
root=rt;
}
int f[N][18],bin[25],tp,deep[N];
inline void pre(int rt,int fa)
{
f[rt][0]=fa;
deep[rt]=deep[fa]+1;
for(int i=1;bin[i]+1<=deep[rt];i++)
{
f[rt][i]=f[f[rt][i-1]][i-1];
}
for(int i=0;i<s[rt].size();i++)
{
if(s[rt][i]!=fa)
pre(s[rt][i],rt);
}
}
inline int LCA(int a,int b)
{
if(deep[a]<deep[b])
{
swap(a,b);
}
for(int i=tp;i>=0;i--)
{
if(deep[f[a][i]]>=deep[b])
a=f[a][i];
}
if(a==b)
return a;
for(int i=tp;i>=0;i--)
{
if(f[a][i]!=f[b][i])
{
a=f[a][i];
b=f[b][i];
}
}
return f[a][0];
}
inline int dis(int a,int b)
{
return deep[a]+deep[b]-deep[LCA(a,b)]*2;
}
inline void DFS3(int rt,int fa,int Vatty)
{
h1[root].push(dis(rt,Vatty));
for(int i=0;i<s[rt].size();i++)
{
int to=s[rt][i];
if(!vis[to]&&to!=fa)
{
DFS3(to,rt,Vatty);
}
}
}
inline void DFS2(int rt,int fa)
{
Vt=fa,vis[rt]=1,h2[rt].push(0);
int siz=totsize;
for(int i=0;i<s[rt].size();i++)
{
int to=s[rt][i];
if(!vis[to])
{
if(size[to]>size[rt])
totsize=siz-size[rt];
else
totsize=size[to];
root=0,DFS1(to,0);
DFS3(root,0,rt);
h2[rt].push(h1[root].top()),DFS2(root,rt);
}
}
if(h2[rt].size()>1)
h3.push(h2[rt].top()+h2[rt].top2());
}
inline void turnoff(int who)
{
int val,tmp;
if(h2[who].size()>1)
{
h3.erase(h2[who].top()+h2[who].top2());
}
h2[who].push(0);
if(h2[who].size()>1)
h3.push(h2[who].top()+h2[who].top2());
for(int rt=who;Vt;rt=Vt)
{
if(h2[Vt].size()>1)h3.erase(h2[Vt].top()+h2[Vt].top2());
if(h1[rt].size())h2[Vt].erase(h1[rt].top());
h1[rt].push(dis(who,Vt));
h2[Vt].push(h1[rt].top());
if(h2[Vt].size()>1)h3.push(h2[Vt].top()+h2[Vt].top2());
}
}
inline void turnon(int who)
{
int val,tmp;
if(h2[who].size()>1)h3.erase(h2[who].top()+h2[who].top2());
h2[who].erase(0);
if(h2[who].size()>1)h3.push(h2[who].top()+h2[who].top2());
//queue empty()后依然有数
for(int rt=who;Vt;rt=Vt)
{
if(h2[Vt].size()>1)h3.erase(h2[Vt].top()+h2[Vt].top2());
h2[Vt].erase(h1[rt].top());
h1[rt].erase(dis(who,Vt));
if(h1[rt].size())h2[Vt].push(h1[rt].top());
if(h2[Vt].size()>1)h3.push(h2[Vt].top()+h2[Vt].top2());
}
}
int main()
{
freopen("hide.in","r",stdin);
freopen("hide.out","w",stdout);
scanf("%d",&n);
register int q,a,b,cnt=n;
for(int i=bin[0]=1;i<=20;++i)bin[i]=bin[i-1]<<1;
while(bin[tp+1]<=n)++tp;
for(int i=1;i<n;++i)
{
scanf("%d%d",&a,&b);
s[a].push_back(b);
s[b].push_back(a);
}
pre(1,0);
maxs[0]=inf,root=0,totsize=n,DFS1(1,0),DFS2(root,0);
scanf("%d",&q);
char X;
while(q--)
{
cin>>X;
if(X=='C')
{
scanf("%d",&a);
if(state[a])++cnt,turnoff(a);
else --cnt,turnon(a);
state[a]^=1;
}
else
{
if(cnt<2)printf("%d\n",cnt-1);
else printf("%d\n",h3.top());
}
}
}