树上博弈,真难。。。。。。
https://blog.csdn.net/lr7682/article/details/100067840
Colon Principle:当树枝在一个顶点上时,用一个非树枝的杆的长度来替代,相当于他们的n异或之和。
#include<iostream> #include<algorithm> using namespace std; const int max_n = 1100; struct edge{ int to, cost, next; }E[max_n << 1]; int head[max_n]; int cnt = 1; void add(int from, int to, int cost) { E[cnt].to = to;E[cnt].cost = cost; E[cnt].next = head[from];head[from] = cnt++; } int dfs(int u,int fa) { int ans = 0; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (e.to == fa)continue; if (e.cost == 1)ans ^= dfs(e.to, u) + 1; else ans ^= dfs(e.to, u) ^ (e.cost & 1); }return ans; } int main() { ios::sync_with_stdio(0); int tcase;cin >> tcase; for (int t = 1;t <= tcase;++t) { fill(head, head + max_n, 0);cnt = 1; int n;cin >> n; for (int i = 1, u, v, w;i < n;++i) { cin >> u >> v >> w;++u;++v; add(u, v, w);add(v, u, w); }cout << "Case " << t << ": "; dfs(1, 1) > 0 ? cout << "Emily\n" : cout << "Jolly\n"; } }