Hihocoder --- 17周 LCA的在线算法

#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;
}