LCA memo 最小共通祖先 lca c++

http://abc014.contest.atcoder.jp/tasks/abc014_4

完全にmemoで保存用

O(N^2)

#include <bits/stdc++.h>

using namespace std;

const int M = 100010;

vector<int> G[M];
int root;
int n,q;
int parent[M];
int depth[M];

void dfs(int v,int p,int d){
	parent[v] = p;
	depth[v] = d;
	for(int i = 0;i < G[v].size();i++){
		if(G[v][i] != p) dfs(G[v][i],v,d + 1);
	}
}

void init(){
	dfs(root,-1,0);
}

int lca(int u,int v){
	while(depth[u] > depth[v])u = parent[u];
	while(depth[v] > depth[u])v = parent[v];
	while(u != v){
		v = parent[v];
		u = parent[u];
	}
	return u;
}

int main(){
	scanf("%d",&n);
	root = 1;
	for(int i = 0;i < n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	init();
	scanf("%d",&q);

	for(int i = 0;i < q;i++){
		int a,b;
		scanf("%d%d",&a,&b);

		int par = lca(a,b);
		printf("%d\n",(depth[a]-depth[par])+(depth[b]-depth[par])+1);
	}
	return 0;
}

O(N log N)

#include <bits/stdc++.h>

using namespace std;

const int M = 100010;
const int MLV = 18; 
vector<int> G[M];
int root;
int n,q;
int parent[MLV][M];
int depth[M];

void dfs(int v,int p,int d){
	parent[0][v] = p;
	depth[v] = d;
	for(int i = 0;i < G[v].size();i++){
		if(G[v][i] != p) dfs(G[v][i],v,d + 1);
	}
}

void init(int V){
	dfs(root,-1,0);
	for(int k = 0;k+1 < MLV;k++){
		for(int v = 1;v <= V;v++){
			if(parent[k][v] < 0) parent[k+1][v] = -1;
			else parent[k+1][v] = parent[k][parent[k][v]];
		}
	}
}

int lca(int u,int v){
	if(depth[u] > depth[v]) swap(u,v);
	for(int k = 0;k < MLV;k++){
		if((depth[v] - depth[u]) >> k & 1){
			v = parent[k][v];
		}
	}
	if(u == v)return u;
	for(int k = MLV-1;k >= 0;k--){
		if(parent[k][u] != parent[k][v]){
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

int main(){
	scanf("%d",&n);
	root = 1;
	for(int i = 0;i < n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	init(n);
	scanf("%d",&q);

	for(int i = 0;i < q;i++){
		int a,b;
		scanf("%d%d",&a,&b);

		int par = lca(a,b);
		printf("%d\n",(depth[a]-depth[par])+(depth[b]-depth[par])+1);
	}
	return 0;
}

RMQでの実装（バグる）
つらい

#include <bits/stdc++.h>

using namespace std;

const int M = 100010;

vector<int> G[M];
int vs[M*2-1];
int depth[M * 2 - 1];
int id[M];
int root;
int K;
int haji;
int seg[4 * M];
void rmq_init(int n_){
	haji = 1;
	while(haji < n_)haji *= 2;
	for(int i = 0;i < haji*2-1;i++){
		seg[i] = -1;
	}
}

void update(int k,int a){
	k += haji - 1;
	seg[k] = a;
	while(k > 0){
	//	seg[k] = min(depth[seg[k*2+1]],depth[seg[k*2+2]]);
		int a = seg[k*2+1],b = seg[k*2+2];
		if(a != -1 && b != -1){
			seg[k] = depth[a] < depth[b] ? a : b;
		}else if(a == -1){
			seg[k] = b;
		}else{
			seg[k] = a;
		}
	}
}

int query(int a,int b,int k,int l,int r){
	if(r <= a || b <= l)return -1;
	if(a <= l && r <= b) return seg[k];
	else{
		int vl = query(a,b,k*2+1,l,(l+r)/2);
		int vr = query(a,b,k*2+2,(l+r)/2,r);
		if(vl == -1){
			return vr;
		}else if(vr == -1){
			return vl;
		}else{
			return (depth[vl] < depth[vr] ? vl : vr);
		}
	}
}
void dfs(int v,int p,int d,int &k){
	id[v] = k;
	vs[k] = v;
	depth[k++] = d;
	for(int i = 0;i < G[v].size();i++){
		if(G[v][i] != p){
			dfs(G[v][i],v,d+1,k);
			vs[k] = v;
			depth[k++] = d;
		}
	}
}

void init(int V){
	int k = 0;
	dfs(root,-1,0,k);
	K = V;
	rmq_init(V*2-1);
}

int lca(int u,int v){
	return vs[query(min(id[u],id[v]),max(id[u],id[v])+1,0,0,haji)];
}

int main(){
	int n,q;
	int root = 1;
	scanf("%d",&n);
	for(int i = 0;i < n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	init(n);
	for(int i = 0;i <= K;i++){
		update(i,i);
	}
	for(int i = 0;i < K;i++){
		printf("%d\n",seg[i]);
	}
	scanf("%d",&q);
	for(int i = 0;i < q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		int par = lca(a,b);
		printf("%d\n",(depth[id[a]] - depth[id[par]]) + (depth[id[b]] - depth[id[par]]) + 1);
	}
	return 0;
}