boj/11437_LCA_DFS.cpp at master · bg-chun/boj · 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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <stdio.h>

typedef struct Vector
{
	int v;
	Vector* next;
}vector;

typedef struct Data
{
	vector* vectors[50010];
	vector vectorNode[100010];
	int vIdx;

	int visited[50010];
	int pId[50010];
	int depth[50010];
}data;

static data workspace;

inline vector* getNewVectorNode(int v)
{
	workspace.vectorNode[workspace.vIdx].v = v;
	return &(workspace.vectorNode[workspace.vIdx++]);
}

static int tmp;
inline int LCA(int a, int b)
{
	//swap
	if (workspace.depth[a] < workspace.depth[b])
	{
		tmp = a;
		a = b;
		b = tmp;
	}

	//a의 depth가 더 깊다. b와 같아질떄까지 올려준다.
	while (workspace.depth[a] != workspace.depth[b])
	{
		a = workspace.pId[a];
	}

	//깊이가 같아졌으면 공통 조상이 나올때까지 반복한다.

	while (a != b)
	{
		a = workspace.pId[a];
		b = workspace.pId[b];
	}

	return a;
}

void dfs_calc(int pid, int id, int depth)
{
	if (workspace.visited[id] == 1)
	{
		return;
	}

	workspace.visited[id] = 1;

	workspace.pId[id] = pid;
	workspace.depth[id] = depth;

	vector* node = workspace.vectors[id];

	while (node)
	{
		if (workspace.visited[node->v] != 1)
		{
			dfs_calc(id, node->v, depth + 1);
		}
		node = node->next;
	}

	return;
}
static int N, M, a, b;
static vector* tmpV;
int main()
{
	//std::cin >> N;
	scanf("%d", &N);


	for (register int i = 1; i < N; i++)
	{
		//std::cin >> a;
		//std::cin >> b;
		scanf("%d", &a);
		scanf("%d", &b);

		if (workspace.vectors[a] == 0)
		{
			workspace.vectors[a] = getNewVectorNode(b);
		}
		else
		{
			tmpV = workspace.vectors[a];
			workspace.vectors[a] = getNewVectorNode(b);
			workspace.vectors[a]->next = tmpV;
		}

		if (workspace.vectors[b] == 0)
		{
			workspace.vectors[b] = getNewVectorNode(a);
		}
		else
		{
			tmpV = workspace.vectors[b];
			workspace.vectors[b] = getNewVectorNode(a);
			workspace.vectors[b]->next = tmpV;
		}

	}

	//void dfs_calc(int pid, int id, int depth)
	dfs_calc(-1, 1, 0);


	M = 0;
	std::cin >> M;

	for (register int i = 0; i < M; i++)
	{
		//std::cin >> a;
		//std::cin >> b;
		scanf("%d", &a);
		scanf("%d", &b);
		printf("%d\n", LCA(a, b));
	}

	return 0;
}