[hiho]#1069 : 最近公共祖先·三 線段樹|樹轉數組

描述：（原題位址：http://hihocoder.com/problemset/problem/1069?sid=601396）

給定一顆樹，給出樹根，以及一些查詢pair，要求輸出每條查詢pair的最近公共節點。

保證所有查詢節點都在這棵樹上。

輸入：第一行一個整數N代表邊數，之後N行每行兩個節點分别是一對父子，其中第一對父子中的父節點是root。

之後是一個整數M代表查詢數，之後M行每行兩個節點代表一次查詢。1<=N,M<=10^5

輸出：對每一個查詢輸出一行結果。

那個，剛寫完上一個題，發現這個簡直是一毛一樣啊，輸入輸出都沒改~這是鬧哪樣 = =

看看提示吧。。不看不知道，一看吓一跳，居然要在相同複雜度的情況下寫成線上版本，也就是一次查詢一次輸出！

孤陋寡聞的我又可以長長見識了：

小hi這個天才ACMer首先說了一個大家都知道的事情：最近公共祖先就是兩個節點的深度最小的公共祖先。簡直是廢話。然而第二句就讓人驚奇：找一個範圍内的最小值可以用線段樹。等下，線段樹我有所耳聞，但是那東西不是需要通過數組來建立的嗎？我們現在拿的是一顆樹诶。。然後下面的技巧是照搬的了：深度周遊這棵樹，在進入這棵樹的時候以及從子節點傳回這棵樹的時候都将這棵樹加入到一個數組的結尾，來将一顆樹轉換為數組。這個數組的大小是原來樹的邊數的兩倍。

好吧确實可以這麼轉換，而且轉換之後隻需要找到兩個節點最後出現在數組中的位置之間，深度最小的那個節點就是最近公共祖先了！來理一理這句話：兩個節點最後出現的位置，也就是它們周遊完自己以及自己所有子樹要回到父節點的時刻。由深度周遊的特性，這兩個時刻之間周遊的所有節點都屬于同一個最近公共祖先（包括這個祖先），并且由于這個最近公共祖先的子節點尚未周遊完，是以一定不會有更高層的祖先。

說明了方法的可行性，接着就完成它吧。分四步：

1. 讀入資料，建關系樹；這一步比較簡單。

2. 深度周遊，樹轉數組；在深度周遊的時候為每一個節點初始化深度值，并用一個map記錄每個節點最後出現的下标。

3. 由數組建線段樹；這一步也不複雜，和普通線段樹沒得差。

4. 查詢；也和普通線段樹一樣。

又是看起來複雜的功能，邏輯分析清楚就很簡潔，而且時間複雜度比上次做的離線計算更！低！（250ms）

小hi果然深不可測啊。。。

代碼如下：

// Problems.cpp : Defines the entry point for the console application.
//
#include <sstream>
#include <stdio.h>
#include <functional>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <list>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
const int MAXPRIME = 1000000007;

class TreeNode { // 普通樹
public:
  string name;
  int level;
  vector<TreeNode*> children;
  TreeNode(string n) : name(n), level(0) {}
};
class Node { // 線段樹
public:
  TreeNode *mnode;
  int rangeleft, rangeright, mid;
  Node *left, *right;
  Node(vector<TreeNode*> &data, int l, int r) :
      mnode(NULL),
      left(NULL),
      right(NULL) {
    mid = rangeleft =l, rangeright = r;
    if (l == r) {
      mnode = data[l];
      return;
    }
    mid = (l + r) >> 1;
    left = new Node(data, l, mid);
    right = new Node(data, mid + 1, r);
    if (left->mnode->level < right->mnode->level) {
      mnode = left->mnode;
    } else {
      mnode = right->mnode;
    }
  }
  TreeNode* find(int l, int r) {
    if (l <= rangeleft && r >= rangeright) {
      return mnode;
    }
    if (r <= mid) {
      return left->find(l, r);
    }
    if (l > mid) {
      return right->find(l, r);
    }
    TreeNode *trl = left->find(l, mid);
    TreeNode *trr = right->find(mid + 1, r);
    return trl->level < trr->level ? trl : trr;
  }
};

// turn a tree into an array
void dfs(vector<TreeNode*> &data, map<string, int> &ind, TreeNode *root, int lv) {
  root->level = lv;
  data.push_back(root);
  ind[root->name] = data.size() - 1;
  for (auto &i : root->children) {
    dfs(data, ind, i, lv + 1);
    data.push_back(root);
    ind[root->name] = data.size() - 1;
  }
}


void pro() {
  int n;
  cin >> n;
  string a, b;
  map<string, int> ind;
  vector<TreeNode*> data;
  map<string, TreeNode*> mp;
  n--;
  cin >> a >> b;
  TreeNode *root = new TreeNode(a);
  mp[a] = root;
  mp[b] = new TreeNode(b);
  root->children.push_back(mp[b]);
  while (n--) {
    cin >> a >> b;
    if (mp.find(a) == mp.end()) mp[a] = new TreeNode(a);
    if (mp.find(b) == mp.end()) mp[b] = new TreeNode(b);
    mp[a]->children.push_back(mp[b]);
  }
  dfs(data, ind, root, 0);
  Node *nd = new Node(data, 0, data.size() - 1);
  cin >> n;
  TreeNode *p;
  while (n--) {
    cin >> a >> b;
    int l = ind[a], r = ind[b];
    if (l > r) swap(l, r);
    p = nd->find(l, r);
    cout << p->name << endl;
  }
}

void handle() {
  pro();
}

int main() {

  handle();

  system("PAUSE");

  return 0;
}