BOJ 20506 - Kaisar - 생존

BOJ 20506 - Kaisar - 생존

단순히 트리 DP를 돌려 각 정점이 LCA가 되는 횟수를 계산해준 뒤, 수를 세주면 된다.

void solve() {  
   int n;  
   cin >> n;  
   vi p(n);  
   vvi edges(n);  
   fv(p);  
   int root = -1;  
   for (int i = 0; i < n; i++) {  
      p[i]--;  
      if (p[i] == -1) root = i;  
      else edges[p[i]].pb(i);  
   }  
   vi cnt(n);  
   function<int(int)> fn = [&](int cur) -> int {  
      int ret = 1;  
      int other_cnt = 0;  
      for (int to: edges[cur]) {  
         int subtree = fn(to);  
         cnt[cur] += subtree * other_cnt * 2;  
         other_cnt += subtree;  
         ret += subtree;  
      }  
      cnt[cur] += (ret - 1) * 2 + 1;  
      return ret;  
   };  
   fn(root);  
   debug(cnt);  
   int odd = 0, even = 0;  
   int offset = 0;  
   for (int i = 0; i < n; i++) {  
      int e = cnt[i] / 2;  
      int o = cnt[i] - e;  
      e *= (i + 1);  
      o *= (i + 1);  
      if (offset) {  
         even += o;  
         odd += e;  
      } else {  
         even += e;  
         odd += o;  
      }  
      if (cnt[i] % 2) offset ^= 1;  
   }  
   cout << even << ' ' << odd;  
}