HihoCoder - 1069（LCA的DFS序+ST表求法，模板）

目前完成了2号结构，可能会爆内存，后面会研究一下原因

代码：

// HihoCoder - 1069.cpp
/*
	一颗树结构求lca：
	1.输入一串查询序列，离线Tarjan算法一次算出
	2.一次初始化，之后每次查询快速得到答案，压DFS序之后，每次查询区间深度最小值
	3.初始化ST表，每次倍增求
*/

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
/*-----------------------------ST表部分------------------------------*/
template <class Type>
class StList
{
private:
	bool is_init;
	int st_size;
	vector <Type> v;
	vector <int> log2_floor; // log2_floor[x]表示：(1<<log2_floor[x]) <= x 的最大整数值 log2_floor[x]
	vector < vector<Type> > st; // st[i][j]: min[ v[i] ... v[i+(1<<j)] ) // len = 1<<j
	void getStSize();
	Type min(const Type& l, const Type& r);
	void init();

public:
	StList();
	~StList();
	int size();
	void push_back(Type x);
	Type getMin(int l, int r);
};
template <class Type>
void StList<Type>::getStSize() {
	st_size = 0;
	while ((1 << st_size) < v.size()) {
		st_size++;
	}
}
template <class Type>
Type StList<Type>::min(const Type& l, const Type& r) {
	return l < r ? l : r;
}
template <class Type>
StList<Type>::StList() {
	is_init = true;	st_size = 0;
	v.clear();	st.clear();	log2_floor.clear();
}
template <class Type>
StList<Type>::~StList() {
	v.clear();	st.clear();	log2_floor.clear();
}
template <class Type>
void StList<Type>::init() {
	getStSize();
	st.clear();
	vector <Type> unit(st_size + 1);
	for (int i = 0; i < size(); i++) { // init st[i][0]
		st.push_back(unit);
		log2_floor.push_back(-1);
		;		st[i][0] = v[i];
	}
	for (int i = 1; i < size(); i++) { // init log2_floor;
		log2_floor[i] = log2_floor[i / 2] + 1;
	}
	for (int j = 1; j <= st_size; j++) {
		for (int i = 0; i < st.size(); i++) {
			if (i + (1 << (j - 1)) >= st.size()) {
				break;
			}
			st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	is_init = true;
}
template <class Type>
int StList<Type>::size() {
	return v.size();
}
template <class Type>
void StList<Type>::push_back(Type x) {
	is_init = false;
	v.push_back(x);
}
template <class Type>
Type StList<Type>::getMin(int l, int r) {
	if (is_init == false) {
		init();
	}
	if (l > r || l < 0 || r >= v.size()) {
		return Type();
	}
	int len = (r - l + 1);
	int mov = log2_floor[len];
	return min(st[l][mov], st[r - (1 << mov) + 1][mov]);
}
/*-----------------------------LCA部分------------------------------*/
class TreeLCA
{
public:
	struct node {
		int ID, hight, finalpos; // ID, 高度，回溯时在dfsID中的位置
		vector <int> son;
		bool operator < (const node& other)const {
			return this->hight < other.hight;
		}
	};
	TreeLCA();
	TreeLCA(const vector < pair<int, int> >& edge, int rt);
	int getLCA(int x, int y);
	int getLCA(pair<int, int>q);

private:
	int root;
	vector <node> a;
	vector <int> dfsID; // dfs遍历的顺序，每个边的两个节点都会被存储一次
	StList<node> ST;

	void addEdge(int x, int y);
	void addEdge(pair<int, int> edge);
	void initDFS();
	void dfs(int x, int fa, int h);
};
TreeLCA::TreeLCA() {}
TreeLCA::TreeLCA(const vector < pair<int, int> >& edge, int rt) {
	root = rt;
	a.resize(edge.size() + 2);
	for (int i = 0; i < edge.size() + 2; i++) {
		a[i].ID = i;
	}
	for (int i = 0; i < edge.size(); i++) {
		addEdge(edge[i]);
	}
	initDFS();
	for (int i = 0; i < dfsID.size(); i++) {
		ST.push_back(a[dfsID[i]]);
	}
}
void TreeLCA::addEdge(int x, int y) {
	a[x].son.push_back(y);
	a[y].son.push_back(x);
}
void TreeLCA::addEdge(pair<int, int> edge) {
	int x = edge.first, y = edge.second;
	a[x].son.push_back(y);
	a[y].son.push_back(x);
}
void TreeLCA::initDFS() {
	dfs(root, -1, 1);
}
void TreeLCA::dfs(int x, int fa, int h) {
	a[x].hight = h;
	for (int i = 0; i < a[x].son.size(); i++) {
		if (a[x].son[i] == fa) {
			continue;
		}
		dfsID.push_back(x);
		dfs(a[x].son[i], x, h + 1);
	}
	a[x].finalpos = dfsID.size();
	dfsID.push_back(x);
}
int TreeLCA::getLCA(int x, int y) {
	int l = min(a[x].finalpos, a[y].finalpos), r = max(a[x].finalpos, a[y].finalpos);
	return ST.getMin(l, r).ID;
}
int TreeLCA::getLCA(pair<int, int>q) {
	int l = min(a[q.first].finalpos, a[q.second].finalpos), 
		r = max(a[q.first].finalpos, a[q.second].finalpos);
	return ST.getMin(l, r).ID;
}

int main()
{
	TreeLCA ans;
	map<string, int> mp;
	vector<string> name;
	vector<pair<int, int>> edge;
	int n, m;
	string temp1, temp2;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> temp2;
		if (mp.count(temp1) == 0) {
			mp[temp1] = name.size();
			name.push_back(temp1);
		}
		if (mp.count(temp2) == 0) {
			mp[temp2] = name.size();
			name.push_back(temp2);
		}
		edge.push_back( make_pair(mp[temp1], mp[temp2]) );
	}
	ans = TreeLCA(edge,0);
	cin >> m;
	while (m--) {
		cin >> temp1 >> temp2;
		cout << name[ans.getLCA(mp[temp1], mp[temp2])] << endl;
	}
}