Nearest Common Ancestors

問題

1330 -- Nearest Common Ancestors

感想

• pojってなんか緊張する。わかる人いませんか笑？
• 英語の問題文読むのって英語の勉強にもなるのかな...

考え

まずは、子に対して親がどうであるか、map<子, 親>のようにして記録していく。そして次に、求めたい2つのノードに対して、片方のノードの親をsetに保存していき、もう片方の親をたどる中でsetに格納されているかを調べることで解が得られた。

Accepted Program

#include <iostream>
#include <map>
#include <set>
using namespace std;

int main () {
  int T;
  cin >> T;
  for (int q = 0; q < T; q++) {
    int n;
    cin >> n;
    map<int, int> parent;
    int p, c;
    for (int i = 0; i < n - 1; i++) {
      cin >> p >> c;
      parent[c] = p;      
    }  
    int l, r;
    cin >> l >> r;
    set<int> ll;
    ll.insert(l);
    while (parent[l] != 0) {
      ll.insert(l);
      l = parent[l];  
    }
    ll.insert(l);
    if (ll.count(r) == 1) {
      cout << r << endl;
    }
    else {
      bool ok = true;
      while (parent[r] != 0) {
        if (ll.count(r) == 1) {
          cout << r << endl;
          ok = false;
          break;  
        }  
        r = parent[r];
      }
      if (ll.count(r) == 1 && ok) {
        cout << r << endl;
      }
    }
  } 
}