D - Fennec VS. Snuke

問題文

atcoder.jp

解き直すと別の解法で解けたので書きます。

解法

ゲームには貪欲法が存在し、からに向かう頂点を埋めていくのが最適です。
与えられるグラフは木なので、任意の頂点に関して、がただ一つ存在します。
したがって、に含まれる頂点のうちどれがに含まれるか、に含まれるかを計算します。
後はにくっついている頂点を数えて数を比較すればどちらが勝つかわかります。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
using namespace std;
signed main(){
    int n; cin >> n;
    vector<vector<int>>edge(n);
    rep(i,n-1){
        int s,t; cin >> s >> t;
        edge[--s].push_back(--t);
        edge[t].push_back(s);
    }
    vector<bool>visit(n,false);
    vector<bool>ispath(n,false);
    function<bool(int)> dfs = [&](int v){
        visit[v] = true;
        bool flag = (v == n-1);
        for(auto nv : edge[v]){
            if(visit[nv])continue;
            if(dfs(nv))flag = true;
        }
        return ispath[v] = flag;
    };
    dfs(0);
    // all vertex was checked.
    int margin = accumulate(all(ispath),0LL) - 2;
    margin = margin / 2 + margin % 2;
    vector<int>grid(n,-1);
    function<int(int,int)>cntup = [&](int v, int atrb){
        int res = 1;
        grid[v] = atrb;
        for(auto nv : edge[v]){
            if(grid[nv] != -1)continue;
            if(ispath[nv] == false or atrb == 1) res += cntup(nv,atrb);
            else if(ispath[nv] and margin > 0 )--margin,res += cntup(nv,atrb);
        }
        return res;
    };
    int f = cntup(0,0), s = cntup(n-1,1);
    assert(f + s == n);
    cout << (f > s ? "Fennec" : "Snuke") << endl;
}