题解：AT_abc398_e [ABC398E] Tree Game

SunburstFan · 2025-03-23 10:44:56 · 题解

E - Tree Game

题目大意

给定一棵有 N 个节点的树，编号为 1 到 N。游戏玩家（你）和高桥君轮流向图中添加新的边 (i,j)，但只能添加不在图中已有边中出现、且不会形成奇环的边。当一位玩家无法进行有效操作时，该玩家失败。你的任务是决定先手或后手，并与高桥君交互，给出你的操作，直到获胜后结束游戏。

解题思路

用 BFS 为每个顶点染色，以区分出两个不交叠的颜色集合（把树看做二分图）。然后，对于颜色不同且尚未直接相连的一对节点 (i, j)，收集到集合 m。若集合大小为奇数则先手，否则后手。随后在游戏循环中，两方轮流从 m 中移除可行的一对节点并输出；对手的操作则从输入中读取并从 m 中移除。

代码：

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    vector<vector<bool>>e(n+1,vector<bool>(n+1,0));

    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        e[u][v]=e[v][u]=1;
    }

    vector<int>c(n+1,-1);
    queue<int>q;
    c[1]=0;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(c[v]==-1){
                c[v]=c[u]^1;
                q.push(v);
            }
        }
    }

    set<pair<int,int>>m;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(c[i]!=c[j]&&!e[i][j]){
                m.insert({i,j});
            }
        }
    }

    bool f=(m.size()%2==1);
    if(f){
        cout<<"First\n";
        cout.flush();
    }
    else{
        cout<<"Second\n";
        cout.flush();
    }

    bool t=f;
    while(1){
        if(t){
            if(m.empty())break;
            auto p=*m.begin();
            m.erase(m.begin());
            cout<<p.first<<" "<<p.second<<"\n";
            cout.flush();
        }
        int u,v;
        cin>>u>>v;
        if(u==-1&&v==-1)break;
        pair<int,int>p=(u<v)?make_pair(u,v):make_pair(v,u);
        if(m.find(p)!=m.end()){
            m.erase(p);
        }
        t=1;
    }

    return 0;
}