By yusijia

Updated:

Contents

直接Tarjan，不过注意下节点是1 ~ n

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

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 10010;//最大顶点数

int n, root;//实际顶点个数，树根节点
int indegree[MAXN];//顶点入度，用来判断树根
int father[MAXN];//存父亲节点
int ancestor[MAXN];//已访问节点集合的祖先
bool vis[MAXN];

vector<int> tree[MAXN];//领接表存树(不一定是二叉树)
vector<int> query[MAXN];//所有查询的内容

void init()
{
	for(int i = 0; i < MAXN; i++){
		father[i] = i;
		ancestor[i] = i;
	}
	memset(vis, false, sizeof(vis));
}

void inputTree()
{
	scanf("%d", &n);//树的顶点数
	for(int i = 0; i <= n; i++){//n个点：1～n
		tree[i].clear();
		indegree[i] = 0;
	}
	for(int i = 1; i < n; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		tree[x].push_back(y);//tree[x][y]里代表边xy，但存的是x的邻接节点y
		indegree[y]++;
	}
	for(int i = 1; i <= n; i++)if(!indegree[i]){//模板上是从0开始的
		root = i;
		break;
	}
}

void inputQuery()
{
	for(int i = 0; i < n; i++){
		query[i].clear();//清空上次查询
	}
	int m;
	m = 1;
	while(m--){
		int u, v;
		scanf("%d%d", &u, &v);
		query[u].push_back(v);//跟u相关的所有查询(u,v)都会放在query[u]的数组中
		query[v].push_back(u);
	}
}

int finds(int x)
{
	return x == father[x] ? father[x] : father[x] = finds(father[x]);
}

void unions(int x, int y)
{
	int root_x = finds(x);
	int root_y = finds(y);
	father[root_y] = root_x;//这里注意一下，为了方便理解做了个小处理，这个是有顺序的，把x节点的子树y合并到x
}

void Tarjan(int x)//Tarjan算法求解LCA
{
	for(int i = 0; i < tree[x].size(); i++){
		Tarjan(tree[x][i]); //访问子树
		unions(x, tree[x][i]);//将子树节点与根节点x的集合合并，补：因为unions里的小处理和这里放x，y的顺序，所以下面合并后的集合的祖先LCA就为x（就是子树的祖先）
		ancestor[finds(x)] = x;//合并后的集合的祖先LCA为x
	}
	vis[x] = true;//x的子树访问完了
	for(int i = 0; i < query[x].size(); i++){//与根节点x有关的查询
		if(vis[query[x][i]]){//如果查询的另一个节点已访问，则输出结果
			printf("%d\n", ancestor[finds(query[x][i])]);
		}
	}
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        inputTree();
        inputQuery();
        Tarjan(root);
    }
	return 0;
}
Contents