题解 | 小红的树上游戏

#include <iostream> 
#include <vector>

using namespace std;

//对于target的degree是1的情况直接赢，对于 >= 2的情况在整个图只剩target和它的两个叶子节点之前其他的叶子节点随便取得，只需判断是谁最后一步使得其度为1
//注意的是这个无根树每次只取叶子节点是不会把它“分裂成两个”的
int main() {
	int t;
	cin >> t;
	//统计target的度 
	while (t--) {
		int n, target, degree = 0;
		cin >> n >> target;
		int v1, v2;
		for (int i = 0; i < n - 1; i++) {
			cin >> v1 >> v2;
			if (v1 == target || v2 == target) degree++;
		}
		string ans = "lose";
		if (degree == 1 || (n - 1) % 2) ans = "win";
		cout << ans << endl;
	}
}