传送门:

AtCoder

洛谷


题目大意:

现在AB在玩游戏,游戏是在两棵树上进行的,A在树a上的点xB在树b上的点y,两棵树上的点的编号是相同的,只是连边方式不同。

对于奇数轮,A可以选择走到它当前在树a上的点的相邻节点,或者在原地不动,对于偶数轮则是B进行选择,当两个人到达编号相同的点时,游戏结束。

现在A想最大化游戏轮数,B想最小化游戏轮数。问游戏的轮数,如果可以进行无限轮游戏,请输出-1

解题思路:

首先判断-1的情况,游戏可以无限进行下去,当且仅当和A当前所在节点u直接相连的点中存在点v满足在树bdis_{u,v}>2。这个是很显然的,因为当B走到这两个节点中间的时候,A回去就好了。

然后考虑A的最优方案,肯定是在树b上一个距离x最远的节点v_1上等B来找到他,那么对答案的贡献就是dis_{x,v_1},这里的dis指的是在树b上的距离。

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
int n,x,y,ans,vis[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
struct Heavy_Light_Decomposition{
    struct edge{int to,nxt;}e[maxn<<1];int tot,head[maxn];
    int idx,fa[maxn],dfn[maxn],dep[maxn],son[maxn],top[maxn],size[maxn];
    void add(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}
    void insert(int u,int v){add(u,v);add(v,u);}
    void build(int x){
        dep[x]=dep[fa[x]]+1;size[x]=1;int mx=0;
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
            if(v==fa[x])continue;
            fa[v]=x;build(v);size[x]+=size[v];
            if(size[v]>mx)mx=size[v],son[x]=v;
        }
    }
    void dfs(int x){
        if(!x)return ;dfn[x]=++idx;
        top[x]=son[fa[x]]==x?top[fa[x]]:x;
        dfs(son[x]);
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(v!=fa[x]&&v!=son[x])dfs(v);
    }
    int query(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            u=fa[top[u]];
        }if(dep[u]>dep[v])swap(u,v);
        return u;
    }
    int get_dis(int u,int v){return dep[u]+dep[v]-2*dep[query(u,v)];}
}HLD[2];
void init(int S){
    queue<int >q;
    q.push(S);vis[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=HLD[0].head[x],v=HLD[0].e[i].to;i;i=HLD[0].e[i].nxt,v=HLD[0].e[i].to)
            if(!vis[v]&&HLD[0].dep[v]<HLD[1].dep[v])vis[v]=1,q.push(v);
    }
}
void solve(){
    for(int x=1;x<=n;x++){
        if(!vis[x])continue;
        ans=max(ans,HLD[1].dep[x]-1);
        for(int i=HLD[0].head[x],v=HLD[0].e[i].to;i;i=HLD[0].e[i].nxt,v=HLD[0].e[i].to)
            if(HLD[1].get_dis(v,x)>2){puts("-1");return ;}
    }write(ans<<1);
}
int main(){
    n=read();x=read();y=read();
    if(x==y){puts("0");return 0;}
    for(int i=1;i<n;i++)HLD[0].insert(read(),read());
    for(int i=1;i<n;i++)HLD[1].insert(read(),read());
    HLD[0].build(x);HLD[0].dfs(x);HLD[1].build(y);HLD[1].dfs(y);
    init(x);solve();
    return 0;
}

发表评论