题解 P11017 Hide And Seek

前排提示：本题为结论题。本篇题解旨在阐明本人是怎么想到的，并给出一个（自认为）比较易懂的证明。

本文中称 hgcnxn 为“抓的”，Drifty 为“跑的”。

另：尽管写得不少，思维可能还是不太连贯，如果有我没讲明白的地方，欢迎在评论区或者私信问我~

分析思路

看上去题意很绕，各种知道不知道的。但比较通俗地理解一下，其实就是抓的只要无法同时顾及跑的可能出现所有的位置，跑的就一定不会被抓住。

这种题的特殊性质通常是能够引领思路的。因此我们先来考虑这些性质。

性质 A（链）

由于抓的知道跑的的初始位置，所以抓的只要往那个位置走就能把跑的逼死，此时抓的必胜。

性质 B（菊花）

仍然是由于抓的知道跑的的初始位置，因此抓的开局上根节点（如果已经在了直接到下一步）再往跑的的所在方向走，跑的就跑不掉。

性质 C（菊花套链，花蕊度数为 3）

这时情况多了起来。不要慌，耐心地进行分讨就好。

先不妨设每条链都很长但长度有限。这里称靠近“花蕊”的方向为“上”，反方向为“下”。

• 当抓的和跑的在同一条链上时，明显可以分两种情况：
  • 如果抓的在跑的上面，抓的直接往下就可以把跑的逼死；
  • 否则抓的跑到花蕊之后无法确定跑的会往哪条链跑，由题意（抓的无法兼顾所有跑的可能出现的位置时跑的一定不被抓住）跑的一定不会被抓住。
• 当抓的和跑的不在同一条链上时，凭空想的话不是很好想，但实际上可以跟上面的情况进行类比，或者从最终的结果出发，来得到两种情况：
  • 如果跑的可能先抓的一步以上到花蕊，那同样由题意跑的一定不会被抓，因为跑的可以根据抓的到达花蕊后往哪个方向走来决定到底要不要提前跑到花蕊去另一条链；
  • 否则抓的先到达花蕊，由于知道了跑的的初始位置而跑的不可能到达其他的链，因此跑的所在的链可以唯一确定，故跑的会被逼死。

综合上述情况，跑的能够胜利，当且仅当跑的可能先抓的一步（不含）以上到达花蕊。

但是我们这里的前提是每条链足够长，现在考虑链很短的情况。

• 四个点的菊花图：在菊花图的性质中考虑过了，抓的必胜。
• 一条链很长，另两条链只延伸一个点：抓的先走到长链的另一端（即不是菊花花蕊的一端）
  • 先往上走到根节点，这时跑的已经被逼到两个一个点的链中的一个了；
  • 进一个一个点的链再出来，此时跑的不管能不能都不敢上根节点，因为否则下回合直接秒；
  • 同理进另外一个一个点的链再出来，这样就能把跑的逼死。
  • 如图：
• 两条链很长，另一条链只延伸一个点：类似于上面的情况，先从一条长链远离花蕊的一端走到根节点，然后进一个点的链再出来（和刚才一样，此时跑的无法换链）最后再下另一条长链。如图：

综上，性质 C 中“花蕊”所连的三条链都必须“很长”，跑的才能赢。现在我们需要“很长”的定义。

刚才我们说，长度为 1 的链不行，是因为抓的到链底再上来的期间，跑的不能从一条链到达另一条链。所以我们试试长度为 2 的链。

我们发现，此时当抓的下到链底时，跑的可以趁此机会换到另一条链。也就是说，刚才的“很长”其实就是长度大于等于 2。

到这里，我们自然而然地猜想到：

如果图中存在一个和上图结构相同的子图，且跑的能先于抓的到达该子图的“花蕊”处，则会出现上图中的情形，跑的必胜；否则抓的必胜。

然后我们发现，证明其充分性就是上图，证必要性就是我们刚才证明某条链长度为 1 不行的过程。所以说，这个结论是正确的。

枚举每个点及其每条出边，如果存在至少三条出边，满足该边另一端的点度数大于等于 2，即至少还连了另外一个点，则该点为刚才所说的“花蕊”，判断 p 和 q 哪个点到该点更近，如果 q 到该点的距离比 p 到该点的距离小 2 及以上，则跑的必胜；如果所有的这种点都不满足距离关系，则抓的必胜。

距离可以通过遍历进行预处理，每条边最多只会被枚举两次，所以时间复杂度 O(m)。

代码

ll t,n,p,q,u,v,lp[200010],lq[200010];
//lp[i] 和 lq[i] 分别表示从 p 和从 q 到 i 的最短距离
vector<ll> a[200010]; 
void dfs(ll now,ll dep,ll lst,ll op){//遍历求出 lp 和 lq 数组
    if(op)lq[now]=dep;
    else lp[now]=dep;
    for(int i=0;i<a[now].size();i++){
        if(a[now][i]!=lst){
            dfs(a[now][i],dep+1,now,op);
        }
    }
}
bool check(ll now){//判断是否为满足要求的点
    ll tot=0;
    for(int i=0;i<a[now].size();i++){
        if(a[a[now][i]].size()>1)tot++;
        if(tot>2)return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--){
        cin>>n>>p>>q;
        for(int i=1;i<=n;i++){
            a[i].clear();//记得清空
        }
        for(int i=1;i<n;i++){
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        dfs(p,0,-1,0);//预处理距离
        dfs(q,0,-1,1);
        bool flg=0;
        for(int i=1;i<=n;i++){
            if(check(i)&&lp[i]>lq[i]+1){//存在一个符合条件的点跑的就必胜
                flg=1;
                break; 
            }
        }
        if(flg)cout<<"Drifty\n";
        else cout<<"hgcnxn\n";
    }
    return 0;
}