Tapris and Noel play the game on Treeone [yukicoder No.768]

https://yukicoder.me/problems/no/768

前提知識

• バックトラック
• 全方位木DP

考察過程

1. 全頂点についてなにかするやつは全方位木DPを真っ先に疑ってしまう
2. 違う場合の方が多いのだが、今回はそれで行けそう
3. 一般化すると、全頂点の判定はまず1頂点についての判定を考えよう
4. すると、バックトラックで勝敗を決することができることが分かるので、それを全方位木DP化する

解法

https://yukicoder.me/submissions/307929

まず、根の頂点を固定して考えてみる。
すると、子が全て負け状態なら勝ち状態。子に1つでも勝ち状態があるなら負け状態となることが分かる。
これを見つけるのが難しい。
ゲーム系でバックトラックで勝敗を決めるパターンに当てはめるところから考察を始めるといいだろう。
　
そこから、次のdpを考える。
dp[cu] := 頂点cuを根としてゲームを始めたときに0なら負け状態、1なら勝ち状態
dfs1は頂点0を根としてDPを構築している。
　
ここで、全方位木DPのテクを使って、答えを導いていく。
dfs2がそれだ。
全方位木DPでは、親も今見ている頂点の子としてDPが正しく作られている状態を維持しながら、dfsをしていく。
なので、全ての子（親も子として考える）についてdpを見て、負け状態か勝ち状態かを判定する。
次に、全ての子について勝ち状態をカウントしよう。
子供に移るときに、自分のDPを子供用に改変するが、そこで勝ち状態を使う。
もし、勝ち状態の子供が0個ならば、自分のDPはかならず勝ち状態。
もし、勝ち状態の子供が2個以上なら、自分のDPはかならず負け状態。
もし、勝ち状態の子供が1個なら、その子に移動するときは、勝ち状態が0になるので、勝ち状態。
その子以外に移動するときは、勝ち状態が1つできるので、負け状態。

int N;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
#define win 1
#define lose 0
int dp[101010];
int dfs1(int cu, int pa = -1) {
    dp[cu] = win;
    fore(to, E[cu]) if (to != pa) if (dfs1(to, cu) == win) dp[cu] = lose;
    return dp[cu];
}
int ans[101010];
void dfs2(int cu, int pa = -1) {
    ans[cu] = win;
    fore(to, E[cu]) if (dp[to] == win) ans[cu] = lose;

    vector<int> wins;
    fore(to, E[cu]) if (dp[to] == win) wins.push_back(to);

    if (wins.size() == 0) {
        dp[cu] = win;
        fore(to, E[cu]) if (to != pa) dfs2(to, cu);
        return;
    } else if(1 < wins.size()) {
        dp[cu] = lose;
        fore(to, E[cu]) if (to != pa) dfs2(to, cu);
        return;
    } else {
        fore(to, E[cu]) if (to != pa) {
            if(wins[0] == to) dp[cu] = win;
            else dp[cu] = lose;
            dfs2(to, cu);
        }
        return;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    dfs1(0);
    dfs2(0);

    vector<int> v;
    rep(i, 0, N) if (ans[i]) v.push_back(i);
    int n = v.size();
    printf("%d\n", n);
    fore(i, v) printf("%d\n", i + 1);
}