P2056 [ZJOI2007]捉迷藏
题目描述
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由\(N\)个屋子和\(N-1\)条双向走廊组成，这\(N-1\)条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这\(N\)个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i改变第\(i\)个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。G(ame)开始一次游戏，查询最远的两个关灯房间的距离。
输入输出格式
输入格式：
第一行包含一个整数\(N\)，表示房间的个数，房间将被编号为\(1,2,3,\dots,N\)的整数。
接下来\(N-1\)行每行两个整数\(a,b\)，表示房间\(a\)与房间\(b\)之间有一条走廊相连。
接下来一行包含一个整数\(Q\)，表示操作次数。接着\(Q\)行，每行一个操作，如上文所示。
输出格式：
对于每一个操作\(Game\)，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出\(0\)；若所有房间的灯都开着，输出\(-1\)。
说明
对于\(20\%\)的数据， \(N ≤50, M ≤100\)；
对于\(60\%\)的数据， \(N ≤3000, M ≤10000\)；
对于\(100\%\)的数据， \(N ≤100000, M ≤500000\)。
如果get到动态点分的思路了这题应该思路上就比较简单了。
简要的说一下，对每个点维护
分治子树所有黑点到分治树父亲的距离
分治树上每个儿子的子树到自己的最大距离（就是上面一个的最大值的集合
然后外部开一个维护答案。
更新暴力跳节点更新就行了
我最开始用了\(\text{multiset}\)极限数据本地居然跑了\(30s\dots\)
然后改用\(\text{priority_queue}\)就过了(\(\text{queue}\)的思路不错)
struct heap
{
std::priority_queue <int> ins,del;
void erase(){while(!del.empty()&&ins.top()==del.top())ins.pop(),del.pop();}
void push(int x){erase();ins.push(x);}
int top(){erase();return ins.top();}
int size(){return ins.size()-del.size();}
void pop(int x){del.push(x);erase();}
int sum()
{
erase();int ret=ins.top(),las=ret;
ins.pop();erase();ret+=ins.top(),ins.push(las);
return ret;
}
};
Code:
#include <cstdio>
#include <cctype>
#include <queue>
const int N=1e5+10;
int head[N],to[N<<1],Next[N<<1],edge[N<<1],cnt;
int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=x*10+c-'0';c=getchar();}
return x*f;
}
struct heap
{
std::priority_queue <int> ins,del;
void erase(){while(!del.empty()&&ins.top()==del.top())ins.pop(),del.pop();}
void push(int x){erase();ins.push(x);}
int top(){erase();return ins.top();}
int size(){return ins.size()-del.size();}
void pop(int x){del.push(x);erase();}
int sum()
{
erase();int ret=ins.top(),las=ret;
ins.pop();erase();ret+=ins.top(),ins.push(las);
return ret;
}
}mxdis[N],mxson[N],ans;
void add(int u,int v,int w)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
namespace RMQDis
{
int dep[N],dis[N],st[N<<1][19],dfn[N],Log[N<<1],dfs_clock;
void dfs(int now,int fa)
{
dep[now]=dep[fa]+1;
st[dfn[now]=++dfs_clock][0]=now;
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa)
dis[v]=dis[now]+edge[i],dfs(v,now),st[++dfs_clock][0]=now;
}
void init()
{
dfs(1,0);
for(int i=2;i<=dfs_clock;i++) Log[i]=Log[i>>1]+1;
for(int j=1;j<=18;j++)
{
for(int x,y,i=1;i<=dfs_clock-(1<<j)+1;i++)
{
x=st[i][j-1],y=st[i+(1<<j-1)][j-1];
st[i][j]=dep[x]<dep[y]?x:y;
}
}
}
int getdis(int x,int y)
{
int ret=dis[x]+dis[y];
x=dfn[x],y=dfn[y];
if(x>y) std::swap(x,y);
int d=Log[y+1-x],a=st[x][d],b=st[y-(1<<d)+1][d];
return ret-(dis[dep[a]<dep[b]?a:b]<<1);
}
}
int f[N],siz[N],del[N],si,rt,mi;
int n,m,col[N],oncnt;
void dfs1(int now,int fa)
{
siz[now]=1;int mx=0;
for(int v,i=head[now];i;i=Next[i])
if(!del[v=to[i]]&&v!=fa)
dfs1(v,now),siz[now]+=siz[v],mx=mx>siz[v]?mx:siz[v];
mx=mx>si-siz[now]?mx:si-siz[now];
if(mi>mx) mi=mx,rt=now;
}
void dfs2(int now,int w,int fa,int dep)
{
mxdis[w].push(dep);
for(int v,i=head[now];i;i=Next[i])
if(!del[v=to[i]]&&v!=fa)
dfs2(v,w,now,dep+1);
}
void updatains(int now)
{
if(mxson[now].size()>1)
ans.push(mxson[now].sum());
}
void updatadel(int now)
{
if(mxson[now].size()>1)
ans.pop(mxson[now].sum());
}
void divide(int now)
{
del[now]=1;
for(int v,i=head[now];i;i=Next[i])
{
if(!del[v=to[i]])
{
si=siz[v],mi=N;
dfs1(v,0),dfs2(v,rt,0,1),v=rt;
if(mxdis[v].size())
mxson[now].push(mxdis[v].top());
f[v]=now,divide(v);
}
}
mxson[now].push(0);
updatains(now);
}
void Ins(int now)
{
int las=now;
updatadel(now);
mxson[now].push(0);
updatains(now);
while(f[now])
{
updatadel(f[now]);
if(mxdis[now].size()) mxson[f[now]].pop(mxdis[now].top());
mxdis[now].push(RMQDis::getdis(f[now],las));
mxson[f[now]].push(mxdis[now].top());
updatains(now=f[now]);
}
}
void Del(int now)
{
int las=now;
updatadel(now);
mxson[now].pop(0);
updatains(now);
while(f[now])
{
updatadel(f[now]);
mxson[f[now]].pop(mxdis[now].top());
mxdis[now].pop(RMQDis::getdis(f[now],las));
if(mxdis[now].size()) mxson[f[now]].push(mxdis[now].top());
updatains(now=f[now]);
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("dew.out","w",stdout);
n=read();col[n]=1;
for(int u,v,w,i=1;i<n;i++)
{
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
col[i]=1;
}
RMQDis::init();
oncnt=si=n,mi=N,dfs1(1,0),divide(rt);
char op[4];m=read();
for(int u,i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='A')
{
if(oncnt==0) puts("They have disappeared.");
else if(oncnt==1) puts("0");
else printf("%d\n",ans.top());
}
else
{
u=read();
if(col[u]) --oncnt,Del(u);
else ++oncnt,Ins(u);
col[u]^=1;
}
}
return 0;
}
2018.12.5