CompetitivePrograming/LCA-RMQ.cpp at master · taiseiKMC/CompetitivePrograming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <limits.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <cassert>
#include <map>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef long double LD;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))

const int N=100000;
vector<int> graph[N], rmq;
int id[N], depth[N];
bool reach[N];

//dfs before lca.
void dfs(int p, int dep)
{
	reach[p]=true;
	depth[p]=dep;
	id[p]=rmq.size();
	rmq.push_back(p);
	REP(i,graph[p].size())
	{
		if(reach[graph[p][i]]) continue;
		dfs(graph[p][i], dep+1);
		rmq.push_back(p);
	}
}
int lca(int p,int q)
{
	int i,j;
	if(id[p]<id[q])
	{
		i=id[p];
		j=id[q];
	}
	else
	{
		i=id[q];
		j=id[p];
	}

	int midep=N, lowest;
	for(int k=i;k<=j;k++)
		if(depth[rmq[k]] < midep)
		{
			midep = depth[rmq[k]];
			lowest = rmq[k];
		}

	return lowest;
}

int main()
{

	dfs(1, 0);

}