题解 P8943

· · 题解

题意：

首先，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