AT2063 [AGC005E] Sugigma: The Showdown 题解

发布于 28 天前  73 次阅读


题意

题目链接

有一棵红树和一棵蓝树,结点相同而边不同。双方各在某一点,只能在自己颜色的树上移动,红方先手。红方需要最大化游戏轮数,蓝方则需要最小化游戏轮数。求最终游戏轮数。

解析

首先发现,如果存在一条连接 $u,v$ 的红边,且 $u,v$ 两点在蓝树上的距离不小于 $3$,则若红方到达其中某一点且蓝方下一步抓不住他,游戏就会进行无限轮。画图易证,这里不赘述。

因此我们假定目前游戏还尚不能使红方无敌。 我们记一个点 $u$ 在红树上的深度为 $depa_u$,在蓝树上的深度为 $depb_u$,我们发现红方可以走的点一定满足 $depa_u<depb_u$。

证明:在红方不能无敌的情况下,一定不存在红方跨过蓝方到蓝树上深度更低的点的情况(一定会被抓住),因此红方既然绕不过去,那么对于 $depa_u \ge depb_u$ 即蓝方先于红方到达或与红方同时到达的这些点,红方也一定到达不了(一样会被抓)。

同时,如果红方不能无敌,那么显然最优解是在所有可以到达的点中走到在蓝树中最深的那个然后等死。

因此,我们只需先跑一边蓝树处理出所有点的 $depb$,然后判断出哪些点能够使红方无敌(在无敌边上),接着再在红树上进行 dfs,只走那些能走的点,每次统计最优解以及能否无敌即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> R[N],B[N];
struct edge{
    int u,v;
}e[N];
int n,X,Y,depa[N],depb[N],fa[N],ans;
bool win[N];
inline void dfs2(int u,int f){//处理出蓝树上的深度
    fa[u]=f;
    for(int i=0;i<B[u].size();i++){
        int v=B[u][i];if(v==f) continue;
        depb[v]=depb[u]+1;dfs2(v,u);
    }
}
inline void dfs1(int u,int f){
    if(win[u]){//判断是否无敌
        printf("-1");
        exit(0);
    }
    ans=max(ans,depb[u]);
    for(int i=0;i<R[u].size();i++){
        int v=R[u][i];if(v==f) continue;
        depa[v]=depa[u]+1;
        if(depa[v]<depb[v]) dfs1(v,u);//判断是否可走
    }
}
inline bool check(int u,int v){//分类讨论,画图易理解
    if(depb[u]<depb[v]) swap(u,v);
    if(depb[u]==depb[v]){
        if(fa[u]!=fa[v]) return true;
        return false;
    }
    else if(depb[u]==depb[v]+1){
        if(fa[u]!=v) return true;
        return false;
    }
    else if(depb[u]==depb[v]+2){
        if(fa[fa[u]]!=v) return true;
        return false;
    }
    return true;
}
int main(){
    scanf("%d%d%d",&n,&X,&Y);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        R[u].push_back(v);
        R[v].push_back(u);
        e[i].u=u;
        e[i].v=v;
    }
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        B[u].push_back(v);
        B[v].push_back(u);
    }
    dfs2(Y,Y);//先跑蓝树
    for(int i=1;i<n;i++){//统计哪些点可以使红方无敌
        int u=e[i].u,v=e[i].v;
        if(check(u,v)) win[u]=win[v]=1;
    }
    dfs1(X,X);
    printf("%d\n",ans<<1);
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣