Tarjan

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
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long LL;
const int MAXN = 100000 + 5;
struct query
{
	int u, v, ans, index;
	query() { u = v = ans = 0; }
	query(int a, int b, int c) { u = a; v = b; ans = 0; index = c; }
	bool operator< (const query x)const
	{
		if (u == x.u)
			return v < x.v;
		return u < x.u;
	}
};
vector<int>v[MAXN];
int n;
int st[MAXN];
int vis[MAXN];
int gone[MAXN];
vector<int>q[MAXN];
vector<query>qu;
int find(int x)
{
	if (st[x] == x)
		return x;
	return find(st[x]);
}
void dfs(int last, int t)
{
	for (int i = 0; i < v[t].size(); i++)
	{
		if (gone[v[t][i]] == 0)
		{
			gone[v[t][i]] = 1;
			dfs(t, v[t][i]);
		}
	}
	for (int i = 0; i < q[t].size(); i++)
	{
		if (vis[q[t][i]] != 0)
		{
			int ans = find(q[t][i]);
			int a = t;
			int b = q[t][i];
			if (a > b)
				swap(a, b);
			lower_bound(qu.begin(), qu.end(), query(a, b, 0))->ans = ans;
		}
	}
	vis[t] = 1;
	st[t] = last;
}
bool cmp(query a, query b)
{
	return a.index < b.index;
}

int main()
{

	qu.clear();
	memset(gone, 0, sizeof(gone));
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < MAXN; i++)
	{
		st[i] = i;
		q[i].clear();
	}
	int m ;
	scanf("%d%d", &n, &m);//n个点m个操作
	for (int i = 1; i < n; i++)//建边
	{
		int a, b;
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if (a > b)
			swap(a, b);
		qu.push_back(query(a, b, i));
		q[a].push_back(b);
		q[b].push_back(a);
	}
	sort(qu.begin(), qu.end());
	gone[1] = 1;//1 为根
	dfs(1, 1);
	sort(qu.begin(), qu.end(), cmp);
	for (int i = 0; i < qu.size(); i++)
	{
		printf("%d\n", qu[i].ans);
	}
}

欧拉序

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
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long LL;
const int MAXN = 100000 + 5;
vector<int>v[MAXN];//存边
int num[MAXN];//结点的欧拉序
int pre[MAXN];//欧拉序对应的结点
int pos[MAXN];//欧拉序的位置
vector<int>euler;//欧拉序
int vis[MAXN];
int tot;
int tre[MAXN * 8];//线段树
//欧拉序长度==2*n
void dfs(int t)
{
	num[t] = ++tot;
	pre[num[t]] = t;
	euler.push_back(num[t]);
	vis[t] = 1;
	pos[num[t]] = euler.size() - 1;
	for (int i = 0; i < v[t].size(); i++)
	{
		if (vis[v[t][i]] == 0)
		{
			dfs(v[t][i]);
			euler.push_back(num[t]);
		}
	}
}
void build(int t, int l, int r)
{
	if (l == r)
	{
		tre[t] = euler[l];
		return;
	}
	int mid = l + r >> 1;
	build(t << 1, l, mid);
	build(t << 1 | 1, mid + 1, r);
	tre[t] = min(tre[t << 1], tre[t << 1 | 1]);
}
int ans;
void query(int t, int l, int r, int x, int y)
{
	if (l >= x && r <= y)
	{
		ans = min(ans, tre[t]);
		return;
	}
	int mid = l + r >> 1;
	if (y <= mid)
	{
		query(t << 1, l, mid, x, y);
	}
	else if (x > mid)
	{
		query(t << 1 | 1, mid + 1, r, x, y);
	}
	else
	{
		query(t << 1, l, mid, x, y);
		query(t << 1 | 1, mid + 1, r, x, y);
	}
}
int main()
{
	//init
	tot = 0;
	ans = 99999999;
	memset(num, 0, sizeof(num));
	memset(pos, 0, sizeof(pos));
	euler.clear();
	euler.push_back(0);//使得欧拉序数组从1开始数
	for (int i = 0; i < MAXN; i++)
	{
		v[i].clear();
	}
	int n, m;//n个边m个查询
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int root = 1;
	dfs(root);
	build(1, 1, euler.size() - 1);
	for (int i = 0; i < m; i++)
	{
		int U, V;
		scanf("%d%d", &U, &V);
		U = pos[num[U]];
		V = pos[num[V]];
		if (U > V)
			swap(U, V);
		query(1, 1, euler.size() - 1, U, V);
		printf("%d\n", pre[ans]);
	}
}

倍增-在线求LCA

建一棵树，输入u，v，输出lca
dep[i]−−i的深度dep[i]--i的深度
fa[i]−−i的父亲fa[i]--i的父亲
f[i][j]−−i的第2j个祖先f[i][j]--i的第2^j 个祖先

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
int n;
const int MAX = 100000 + 5;
int dep[MAX + 5], vis[MAX + 5], fa[MAX + 5], f[MAX + 5][20];
vector<int>v[MAX];
int LCA(int x, int y) {
	if (dep[x] < dep[y])
		swap(x, y);
	for (int i = 16; i >= 0; i--)
		if (dep[f[x][i]] >= dep[y])
			x = f[x][i];
	if (x == y)
		return x;
	for (int i = 16; i >= 0; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}
void dfs(int t, int deep)
{
	vis[t] = 1;
	dep[t] = deep;
	for (int i = 0; i < v[t].size(); i++)
	{
		int V = v[t][i];
		if (vis[V])continue;
		fa[V] = t;
		f[V][0] = t;
		dfs(V, deep + 1);
	}
}
void init()
{
	memset(f, 0, sizeof(f));
	memset(fa, 0, sizeof(fa));
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i <= MAX; i++)v[i].clear();
}
int main()
{
	scanf("%d", &n);
	init();
	for (int i = 1; i < n; i++)//建图
	{
		int u, b;
		scanf("%d%d", &u, &b);
		v[u].push_back(b);
		v[b].push_back(u);
	}


	dfs(1, 1);
	for (int j = 1; j <= 16; j++)
		for (int i = 1; i <= n; i++)
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++)
	{
		int U, V;
		scanf("%d%d", &U, &V);
		int lca = LCA(U, V);
		printf("%d\n", lca);
	}
}