题解：AT_abc398_e [ABC398E] Tree Game

_sin_ · 2025-03-23 09:02:41 · 题解

观察到题目要求你在一棵树上面加边，要求不出现奇环。容易联想到二分图，而树必然是一个二分图。

每一次加边操作相当于把二分图两边的点连起来，能加的边是有限的。设二分图左部点数为 L，右部点数为 R，能额外加的边有 L\times R-(n-1) 条。

由于你可以决定先手还是后手，而且额外加边的数量是有限的，所以我们看额外的边数量的奇偶性。如果能加的边数量为奇数，你就要选择先手，否则你要选择后手。确定加那条边直接暴力枚举即可。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

const int N = 105;
int n,ok[N][N],sum=0,de[N],sb[2];
vector<int>edge[N],vec[2];
pair<int,int>tmp;

void dfs(int x,int fa){
    sb[(de[x]=de[fa]+1)&1]++;vec[de[x]&1].emplace_back(x);
    for(int y:edge[x])if(y^fa)dfs(y,x);
}

pair<int,int> find_edge(){
    for(int x:vec[0])for(int y:vec[1]){
        if(!ok[x][y])return make_pair(x,y);
    }return make_pair(-1,-1);
}

int main(){sb[0]=sb[1]=0;
    cin>>n;for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        edge[x].emplace_back(y);
        edge[y].emplace_back(x);
        ok[x][y]=ok[y][x]=1;
    }dfs(1,0);sum=sb[0]*sb[1]-(n-1);
    // printf("%d",sum);
    if(sum&1){
        cout<<"First"<<endl;
        int x,y;do{
            tmp=find_edge();
            x=tmp.first,y=tmp.second;
            if(x>y)swap(x,y);
            cout<<x<<" "<<y<<endl;
            ok[x][y]=ok[y][x]=1;
            cin>>x>>y;if(x>0&&y>0)ok[x][y]=ok[y][x]=1;
        }while(x!=-1&&y!=-1);
    }else{
        cout<<"Second"<<endl;int x,y;do{
            cin>>x>>y;if(x>0&&y>0)ok[x][y]=ok[y][x]=1;else break;
            tmp=find_edge();
            x=tmp.first,y=tmp.second;
            if(x>y)swap(x,y);
            cout<<x<<" "<<y<<endl;
            ok[x][y]=ok[y][x]=1;
        }while(x!=-1&&y!=-1);
    }
    return 0;
}