Hihocoder---17週LCAのオンラインアルゴリズム
4597 ワード
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <cstdlib>
#include <stdio.h>
using namespace std;
string x[200005];
int weight[200005];
int segtree[200005][20];
string name[200005][20];
int mycount = 0, mleft = 0, mright = 0;
map<string, int> last;
template <class T>
class Node{
/*
* This is a Tree Node class.
*/
public:
T field, parent;
int depth;
vector<T> son;
Node(){
field = "";
depth = 0;
son.clear();
parent = "";
}
Node(T myfield){
field = myfield;
depth = 0;
son.clear();
parent = "";
}
void add_child(T child){
son.push_back(child);
}
void set_parent(T sparent){
parent = sparent;
}
};
template <class T>
class GenTree{
public:
Node<T> *root;
map<T, Node<T>* > nodes;
GenTree(){}
GenTree(T root_field){
root = new Node<T>(root_field);
root->parent = root_field;
nodes.insert(pair<T, Node<T>* >(root_field, root));
}
Node<T>* add_node(T field, T parent = ""){
Node<T> *node = new Node<T>(field);
nodes[field] = node;
if (parent!= ""){
nodes[parent]->add_child(field);
node->parent = parent;
}
else
node->parent = field;
return node;
}
void dfs(T field, int depth){
x[mycount++] = field;
nodes[field]->depth = depth;
int size = nodes[field]->son.size();
if (size != 0){
for (int i=0; i<size; i++){
T cur_son = nodes[field]->son[i];
dfs(cur_son, depth + 1);
x[mycount++] = field;
}
}
last[field] = mycount;
}
};
int cal_pow(int x, int y){
if (y == 1)
return x;
else if (y == 0)
return 1;
if (y % 2 == 0){
int temp_value = cal_pow(x, y/2);
return temp_value * temp_value;
}
else{
int temp_value = cal_pow(x, (y-1)/2);
return temp_value * temp_value * x;
}
}
int findmax(int len){
int count = -1;
while (len > 0){
count++;
len = (len >> 1);
}
return count;
}
int main()
{
GenTree<string> mytree;
int n, m, len, maxT, templen;
string name1, name2, root;
cin>>n;
for (int i=0; i<n; i++){
cin>>name1>>name2;
if (i==0){
root = name1;
mytree.add_node(name1);
mytree.add_node(name2, name1);
}
else
mytree.add_node(name2, name1);
}
mytree.dfs(root, 1);
for (int j=0; j<=findmax(2*n+1); j++)
for (int i=1; i<=2*n+1; i++) {
len = cal_pow(2, j);
if (j == 0){
segtree[i][j] = mytree.nodes[x[i-1]]->depth;
name[i][j] = x[i-1];
}
else if ((i + len/2) <= (2*n+1)){
if (segtree[i][j-1] > segtree[i+len/2][j-1]){
segtree[i][j] = segtree[i+len/2][j-1];
name[i][j] = name[i+len/2][j-1];
}else{
segtree[i][j] = segtree[i][j-1];
name[i][j] = name[i][j-1];
}
}
}
cin>>m;
for (int i=0; i<m; i++){
cin>>name1>>name2;
if (last[name1] > last[name2]){
mleft = last[name2];
mright = last[name1];
}else{
mleft = last[name1];
mright = last[name2];
}
len = mright - mleft + 1;
maxT = findmax(len);
templen = cal_pow(2, maxT);
if (segtree[mleft][maxT] > segtree[mright - templen + 1][maxT])
cout<<name[mright - templen + 1][maxT]<<endl;
else
cout<<name[mleft][maxT]<<endl;
}
return 0;
}