【洛谷P2056】捉迷藏

2021年09月15日 阅读数:3
这篇文章主要向大家介绍【洛谷P2056】捉迷藏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
题目

题目连接:https://www.luogu.com.cn/problem/P2056
Jiajia 和 Wind 是一对恩爱的夫妻,而且他们有不少孩子。某天,Jiajia、Wind 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由 \(N\) 个屋子和 \(N-1\) 条双向走廊组成,这 \(N-1\) 条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的,孩子们负责躲藏,Jiajia 负责找,而 Wind 负责操纵这 \(N\) 个屋子的灯。在起初的时候,全部的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,可是为了增长刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia 但愿知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。
咱们将以以下形式定义每一种操做:c++

  • C(hange) i 改变第 \(i\) 个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。
  • G(ame) 开始一次游戏,查询最远的两个关灯房间的距离。

\(n\leq 10^5,m\leq 5\times 10^5\)ide

思路

建出点分树,对于点分树上每个点,维护两个堆 \(q1,q2\)。其中 \(q1\) 放点分树上在这个点 \(x\) 为根的子树中,全部点到点分树上 \(x\) 父亲的距离。\(q2\) 放点 \(x\) 全部子树的堆的最大值。
那么显然答案就是每个点的 \(q2\) 的最大值和次大值之和的最大值。因此咱们再开一个堆存全部点答案的最大值。
对于一次修改操做,咱们从 \(x\) 往上跳父亲,更新它与父亲的堆便可。
对于查询操做,就直接输出答案堆的堆顶。注意只有一个关灯房间和没有关灯房间须要特判。
可是普通的堆是不支持删除的,因此咱们再开三个堆分别对应前文三个堆,若是要在某一个堆中删除,那么就在其对应的堆中插入,须要时不断判断两个堆顶是否是相同便可。
时间复杂度 \(O(m\log^2 n)\)spa

代码

常数不是很优秀,开了 O2 才过。code

#include <bits/stdc++.h>
using namespace std;

const int N=100010,LG=18,Inf=1e9;
int n,m,rt,tot,cnt,head[N],fa[N],dep[N],maxp[N],size[N],f[N][LG+1];
bool vis[N];
char ch[3];
priority_queue<int> q1[N],q2[N],d1[N],d2[N],qans,dans;

struct edge
{
	int next,to;
}e[N*2];

void add(int from,int to)
{
	e[++tot]=(edge){head[from],to};
	head[from]=tot;
}

void dfs1(int x,int _fa)
{
	f[x][0]=_fa; dep[x]=dep[_fa]+1;
	for (int i=1;i<=LG;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (v!=_fa) dfs1(v,x);
	}
}

void findrt(int x,int _fa,int sum)
{
	size[x]=1; maxp[x]=0;
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (!vis[v] && v!=_fa)
		{
			findrt(v,x,sum);
			size[x]+=size[v];
			if (size[v]>maxp[x]) maxp[x]=size[v];
		}
	}
	if (sum-size[x]>maxp[x]) maxp[x]=sum-size[x];
	if (maxp[x]<maxp[rt]) rt=x;
}

void dfs2(int x,int _fa,int sum)
{
	vis[x]=1; fa[x]=_fa;
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (!vis[v])
		{
			int s=(size[v]<size[x])?size[v]:sum-size[x];
			rt=0;
			findrt(v,0,s); dfs2(rt,x,s);
		}
	}
}

int lca(int x,int y)
{
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=LG;i>=0;i--)
		if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (int i=LG;i>=0;i--)
		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
} 

void updans(int x,bool flag)
{
	if (!q2[x].size()) return;
	int tmp=q2[x].top(); q2[x].pop();
	while (q2[x].size() && d2[x].size() && q2[x].top()==d2[x].top())
		q2[x].pop(),d2[x].pop();
	if (!flag && q2[x].size()) qans.push(q2[x].top()+tmp);
	if (flag && q2[x].size()) dans.push(q2[x].top()+tmp);
	q2[x].push(tmp);
}

void update(int x,bool flag)
{
	updans(x,1);
	if (flag) d2[x].push(0);
		else q2[x].push(0);
	while (q2[x].size() && d2[x].size() && q2[x].top()==d2[x].top())
		q2[x].pop(),d2[x].pop();
	updans(x,0);
	for (int i=x;fa[i];i=fa[i])
	{
		int dis=dep[x]+dep[fa[i]]-2*dep[lca(x,fa[i])];
		updans(fa[i],1);
		if (q1[i].size()) d2[fa[i]].push(q1[i].top());
		if (flag) d1[i].push(dis);
			else q1[i].push(dis);
		while (q1[i].size() && d1[i].size() && q1[i].top()==d1[i].top())
			q1[i].pop(),d1[i].pop();
		if (q1[i].size()) q2[fa[i]].push(q1[i].top());
		while (q2[fa[i]].size() && d2[fa[i]].size() && q2[fa[i]].top()==d2[fa[i]].top())
			q2[fa[i]].pop(),d2[fa[i]].pop();
		updans(fa[i],0);
	}
	while (qans.size() && dans.size() && qans.top()==dans.top())
		qans.pop(),dans.pop();
}

int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	rt=0; maxp[0]=Inf;
	dfs1(1,0);
	findrt(1,0,n); dfs2(rt,0,n);
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)
		update(i,0);
	cnt=n;
	scanf("%d",&m);
	while (m--)
	{
		scanf("%s",ch);
		if (ch[0]=='G')
		{
			if (!cnt) printf("-1\n");
			else if (cnt==1) printf("0\n");
			else printf("%d\n",qans.top());
		}
		else
		{
			int x;
			scanf("%d",&x);
			vis[x]^=1;
			update(x,vis[x]);
			if (vis[x]==1) cnt--;
				else cnt++;
		}
	}
	return 0;
}