POJ 3437 - Tree Grafting

http://poj.org/problem?id=3437

概要

根つき木が与えられるので，初期状態での木の高さと以下の手順に従って二分木に変換した後の木の高さを答える．

1. すべてのエッジを取り除く
2. 各ノードについて，その最初の子を左側の子とする
3. 各ノードについて，その次の兄弟ノードを右側の子とする

制約

• 2 <= ノード数 <= 10^4

解法

ノード n の変換前の高さを h1, 変換後の高さを h2 とすると，変換前の木において

• h1(n) = max [h1(c) + 1 for each c in children]
• h2(n) = max h2(c + i) for each c in children

で計算できる．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 pair<int,int> parse(string::const_iterator& it, const string::const_iterator& last)
 6 {
 7   int h1 = 0, h2 = 0;
 8   int i = 0;
 9   while (it != last && *it == 'd') {
10     ++it;
11     const pair<int,int> r = parse(it, last);
12     h1 = max(h1, r.first + 1);
13     h2 = max(h2, ++i + r.second);
14   }
15   if (it != last && *it == 'u') {
16     ++it;
17   }
18   return make_pair(h1, h2);
19 }
20 
21 int main()
22 {
23   ios::sync_with_stdio(false);
24   string line;
25   for (int Ti = 1; getline(cin, line) && line != "#"; Ti++) {
26     string::const_iterator it = line.begin(), last = line.end();
27     const pair<int,int> r = parse(it, last);
28     cout << "Tree " << Ti << ": " << r.first << " => " << r.second << endl;
29   }
30   return 0;
31 }