BOJ 15900 - 나무 탈출

BOJ 15900 - 나무 탈출

모든 경로에 있는 모든 간선의 개수의 합이 2로 나누어 떨어진다면 No고 아니라면 Yes이다.

구현이 갑자기 꼬여서 계속 틀렸다…

void solve() {  
   int n;  
   cin >> n;  
   vvi edges(n);  
   for (int i = 0; i < n - 1; i++) {  
      int u, v;  
      cin >> u >> v, u--, v--;  
      edges[u].pb(v), edges[v].pb(u);  
   }  
  
  
   // 자신의 서브트리에 있는 리프노드까지 갈 때 모든 경로에 있는 간선의 수의 합  
   int ans = 0;  
   function<int(int, int)> fn = [&](int cur, int p) -> int {  
      if (cur != 0 && sz(edges[cur]) == 1) return 1;  
      int sum = 0, leaf = 0;  
      for (int to: edges[cur]) {  
         if (to == p) continue;  
         int l = fn(to, cur);  
         leaf += l;  
         ans = (ans + l) & 1;  
      }  
      ans = (ans + sum) & 1;  
      return leaf;  
   };  
  
   fn(0, -1);  
   cout << (ans ? "Yes" : "No");  
}