自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:54:06，当前版本为作者最后更新于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;
}