P10039

Loser_Syx · 2024-01-25 14:14:45 · 题解

考虑小 I 获胜的情况，对于当前节点 i，如果可以令小 i 获胜的方案不止 1 种，那么小 J 就算封锁通道也不能使小 I 无法获胜了，此时小 I 到这个节点时必胜，除了令初始时的叶子节点可以获胜外，这个节点 i 我们也认为可以获胜。

如果最后认为节点 1 也是必胜节点的话，那么小 I 就有赢的方案。

vector<int> g[100005];
int dfs(int u, int fa){
    if (g[u].size() == 1) return 1;
    int cnt = 0;
    for (const int i : g[u]){
        if (i == fa) continue;
        cnt += dfs(i, u);
    }
    return cnt >= 2;
}
signed main() {
    int n = read();
    for (int i = 1, u, v; i < n; i++) {
        read(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    puts(dfs(1, -1) ? "You win, temporarily." : "Wasted.");
    return 0;
}