自动搬运

查看原文

来自洛谷，原作者为

	HYdroKomide I hate unfair games.

搬运于2025-08-24 22:43:58，当前版本为作者最后更新于2023-01-15 22:56:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

首先，$n$ 个结点、$n$ 条边的无向图。

我们充分发挥人类智慧，想到，树有 $n-1$ 条边呀！所以这个图就是一棵树加了一条边，组成了一个环，又称基环树。

思路：

我们知道图里必然有且只有一个环，这个环的大小还大于 $4$。所以如果逃离者 $A$ 在监守者 $B$ 堵住路之前到达环上的任意一点，就一定能把监守者绕死。

我们知道图里只有一个环，所以除了环上以外的点都只能通向环上的一个点。我们称 $A$ 第一次踏上环的地点为 $fa_A$。若 $B$ 能够抢先，或者与 $A$ 同时到达 $fa_A$，那么 $A$ 必输。否则，$A$ 必胜。

那么，我们需要知道的，就是 $A$ 与环的距离 $dep_A$、$A$ 踏上环的位置 $fa_A$、$B$ 与环的距离 $dep_B$、$B$ 踏上环的位置 $fa_B$、$A$ 踏上位置与 $B$ 踏上位置的距离 $dist(fa_A,fa_B)$。如果该点在环上，则 $dep$ 值为 $0$。

当 $dep_A \le dist(fa_A,fa_B)+dep_B$，监守者就会堵住门吃掉 $A$。反之 $A$ 可以逃入环中绕杀监守者。

于是，预处理这一堆就行啦！

分解步骤：

1. 分离出图中的环。
2. 对于每个环上的点，遍历其子孙，预处理距离。
3. 预处理环上点互相的距离。

当然，如果 $A$ 已经在环上，肯定有救，可以先特判但没必要。

其实这个方法冗杂比较多，所以代码显得长。具体可参见注释。

程序如下：

#include<cstdio>
#include<vector>
#include<cmath>
const int N=2e5+1;
using namespace std;
int n,q,fd,f[N],dep[N],cnt,sw[N];
bool vis[N],cir[N];
vector<int>g[N];
void dfs1(int x,int fa){//第一个 dfs，找到所有环上的点并标记
	if(vis[x]==true){//如果回到老地方，说明有环了
		fd=x;
		cir[x]=true;
		sw[x]=++cnt;//给环上的点依次打上标记，方便后面查询环上两点的距离
		return;
	}
	vis[x]=true;
	int u=g[x].size();
	for(int i=0;i<u;i++){
		int v=g[x][i];
		if(v!=fa)dfs1(v,x);
		if(fd!=0){
			if(fd==x)fd=0;
			if(!cir[x]){
				cir[x]=true;//回溯的时候就可以继续打标记
				sw[x]=++cnt;
			}
			break;
		}
	}
	return;
}
void dfs2(int old,int x,int fa){//处理所有非环上点与环的距离（深度）
	f[x]=old;//存踏上环的地点
	dep[x]=dep[fa]+1;
	int u=g[x].size();
	for(int i=0;i<u;i++){
		int v=g[x][i];
		if(!cir[v]&&g[x][i]!=fa)dfs2(old,v,x);
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);//vector 连边
	}
	dfs1(1,0);
	dep[0]=-1;
	for(int i=1;i<=n;i++)
		if(cir[i])//对于所有环上的点，进行第二个 dfs
			dfs2(i,i,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		int st=f[x],ed=f[y];//踏上环的两地
		int len=abs(sw[st]-sw[ed]);//环上两地之间的距离
		if(len>cnt/2)len=cnt-len;
		if(cir[x]||dep[x]<dep[y]+len)printf("Survive\n");
		else printf("Deception\n");
	}
	return 0;
}

THE END