ST表

树状数组

主要用于前缀和查询和单点更新

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
class FenwickTree//树状数组，tree的索引从1开始 
{
private:
	 vector<int> tree;
	 int n;
public:
	FenwickTree(int size) : n(size), tree(size + 2, 0) {}
	void add(int x, int k = 1)
	{
		while(x <= n)
		{
			tree[x] += k;
			x += x & -x;
		}
	}	
	int ask(int x)
	{
		int sum = 0;
		while(x)
		{
			sum += tree[x];
			x -= x & -x;
		}
		return sum;
	}
}; 
//初始化
FenwickTree ft(N);//N表示a[i]的最大取值

线段树

区间求最大值

区间修改，区间查询（有懒标记）

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
class SegmentTree//数组下标从0开始 
{
private:
	vector<int> tree;
	vector<int> lazy;
	int n;
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = nums[s];
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = max(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	void pushdown(int u)
	{
		if(lazy[u] != INT_MIN)
		{
			tree[2 * u + 1] = lazy[u];
			lazy[2 * u + 1] = lazy[u];
			tree[2 * u + 2] = lazy[u];
			lazy[2 * u + 2] = lazy[u];
			lazy[u] = INT_MIN;
		}
	}
	
	void updateRange(int u, int s, int e, int l, int r, int val)
	{
		if(l > e || r < s) return;
		if(l <= s && r >= e)
		{
			tree[u] = val;
			lazy[u] = val;
			return;
		}
		pushdown(u);
		int mid = (s + e) >> 1;
		updateRange(2 * u + 1, s, mid, l, r, val);
		updateRange(2 * u + 2, mid + 1, e, l, r, val);
		tree[u] = max(tree[2 * u + 1], tree[2 * u + 2]);
	}
	
	int queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return INT_MIN;
		if(l <= s && r >= e) return tree[u];
		pushdown(u);
		int mid = (s + e) >> 1;
		int left = queryRange(2 * u + 1, s, mid, l, r);
		int right = queryRange(2 * u + 2, mid + 1, e, l, r);
		return max(left, right); 
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n, INT_MIN);
		lazy.resize(4 * n, INT_MIN);
		build(nums, 0, 0, n - 1);
	}
	void update(int l, int r, int val)
	{
		updateRange(0, 0, n - 1, l, r, val);
	}
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, l, r);
	}
};

区间最大连续子串和

单点修改，区间查询（不用懒标记）

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
class SegmentTree
{
private:
	struct Node
	{
		int sum, tmax, lmax, rmax;	
	};
	vector<Node> tree;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		t.lmax = max(l.lmax, l.sum + r.lmax);
		t.rmax = max(r.rmax, r.sum + l.rmax);
		t.tmax = max({l.tmax, r.tmax, l.rmax + r.lmax});
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s], nums[s], nums[s], nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	//单点修改 
	void updateRange(int u, int s, int e, int idx, int val)
	{
		if(s == e) tree[u] = {val, val, val, val};
		else
		{
			int mid = (s + e) >> 1;
			if(idx <= mid)
				updateRange(u * 2 + 1, s, mid, idx, val);
			else 
				updateRange(u * 2 + 2, mid + 1, e, idx, val);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	Node queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return {0, INT_MIN, INT_MIN, INT_MIN};
		if(l <= s && r >= e) return tree[u];
		int mid = (s + e) >> 1;
		Node left = queryRange(u * 2 + 1, s, mid, l, r);
		Node right = queryRange(u * 2 + 2, mid + 1, e, l, r);
		return merge(left, right);
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}	
	
	void update(int idx, int val)
	{
		updateRange(0, 0, n - 1, idx, val);
	}
	
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, l, r).tmax;
	}
};

区间最大公约数

区间修改，区间查询

利用差分数组将区间修改改成单点修改

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
class SegmentTree
{
private:
	struct Node
	{
		int gcd, sum;
	};
	vector<Node> tree;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		t.gcd = __gcd(abs(l.gcd), abs(r.gcd));
        //因为差分数组可能是负数，但是gcd应该是正数，所以需要取abs
        //因为要对数组进行区间修改，所以不能直接对差分数组取abs
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s], nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	//单点修改 
	void updateRange(int u, int s, int e, int idx, int val)
	{
		if(s == e)
		{
			tree[u].sum += val;
			tree[u].gcd += val;
		}
		else
		{
			int mid = (s + e) >> 1;
			if(idx <= mid)
				updateRange(u * 2 + 1, s, mid, idx, val);
			else 
				updateRange(u * 2 + 2, mid + 1, e, idx, val);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	Node queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return {0, 0};//gcd返回0，因为0与任何数的gcd都是任何数
		if(l <= s && r >= e) return tree[u];
		int mid = (s + e) >> 1;
		Node left = queryRange(u * 2 + 1, s, mid, l, r);
		Node right = queryRange(u * 2 + 2, mid + 1, e, l, r);
		return merge(left, right);
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}	
	
	void update(int idx, int val)
	{
		updateRange(0, 0, n - 1, idx, val);
	}
	
	int query(int l, int r)
	{
		return __gcd(queryRange(0, 0, n - 1, l + 1, r).gcd, queryRange(0, 0, n - 1, 0, l).sum);
	}
};

区间和（区间加）

区间修改，区间查询（有懒标记）

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
class SegmentTree
{
private:
	struct Node
	{
		int sum;
	};
	struct Node2
	{
		int sum;
	};
	vector<Node> tree;
	vector<Node2> lazy;
	int n;
	
	Node merge(const Node& l, const Node& r)
	{
		Node t;
		t.sum = l.sum + r.sum;
		return t;
	}
	
	void build(const vector<int>& nums, int u, int s, int e)
	{
		if(s == e) tree[u] = {nums[s]};
		else
		{
			int mid = (s + e) >> 1;
			build(nums, u * 2 + 1, s, mid);
			build(nums, u * 2 + 2, mid + 1, e);
			tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
		}
	}
	
	void pushdown(int u, int s, int e, int mid)
	{
		if(lazy[u].sum != 0)
		{
			tree[2 * u + 1].sum += lazy[u].sum * (mid - s + 1);
			lazy[2 * u + 1].sum += lazy[u].sum;
			tree[2 * u + 2].sum += lazy[u].sum * (e - mid);
			lazy[2 * u + 2].sum += lazy[u].sum;
			lazy[u].sum = 0;
		}
	}
	
	void updateRange(int u, int s, int e, int l, int r, int val)
	{
		if(l > e || r < s) return;
		if(l <= s && r >= e)
		{
			tree[u].sum += val * (e - s + 1);
			lazy[u].sum += val;
			return;
		}
		int mid = (s + e) >> 1;
		pushdown(u, s, e, mid);
		updateRange(u * 2 + 1, s, mid, l, r, val);
		updateRange(u * 2 + 2, mid + 1, e, l, r, val);
		tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
	}
	
	int queryRange(int u, int s, int e, int l, int r)
	{
		if(l > e || r < s) return 0;
		if(l <= s && r >= e) return tree[u].sum;
		int mid = (s + e) >> 1;
		pushdown(u, s, e, mid);
		return queryRange(u * 2 + 1, s, mid, l, r) + queryRange(u * 2 + 2, mid + 1, e, l, r); 
	}
public:
	SegmentTree(const vector<int>& nums)
	{
		n = nums.size();
		tree.resize(4 * n);
		lazy.resize(4 * n);
		build(nums, 0, 0, n - 1);
	}
	
	void update(int l, int r, int val)
	{
		updateRange(0, 0, n - 1, l, r, val);
	}
	int query(int l, int r)
	{
		return queryRange(0, 0, n - 1, l, r);
	}
};

区间和（区间加乘）

  1. pushdown中需要先乘后加，即先处理lazy[u].mul后处理lazy[u].add
  2. 在update中lazy[u].add = (lazy[u].add * mul + add) % mod;加法的懒标记也需要乘mul
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
class SegmentTree
{
private:
    struct Node
    {
        int sum;
    };
    struct LazyNode
    {
        int add, mul;
    };
    vector<Node> tree;
    vector<LazyNode> lazy;
    int n;
    int mod;

    Node merge(const Node& l, const Node& r)
    {
        Node t;
        t.sum = (l.sum + r.sum) % mod;
        return t;
    }

    void build(const vector<int>& nums, int u, int s, int e)
    {
        lazy[u].mul = 1;
        lazy[u].add = 0;
        if(s == e) tree[u] = {nums[s] % mod};
        else
        {
            int mid = (s + e) >> 1;
            build(nums, u * 2 + 1, s, mid);
            build(nums, u * 2 + 2, mid + 1, e);
            tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
        }
    }

    void pushdown(int u, int s, int e, int mid)
    {
        if(lazy[u].mul != 1 || lazy[u].add != 0)
        {
            // 处理左子树
            tree[u * 2 + 1].sum = (tree[u * 2 + 1].sum * lazy[u].mul + lazy[u].add * (mid - s + 1)) % mod;
            lazy[u * 2 + 1].mul = (lazy[u * 2 + 1].mul * lazy[u].mul) % mod;
            lazy[u * 2 + 1].add = (lazy[u * 2 + 1].add * lazy[u].mul + lazy[u].add) % mod;

            // 处理右子树
            tree[u * 2 + 2].sum = (tree[u * 2 + 2].sum * lazy[u].mul + lazy[u].add * (e - mid)) % mod;
            lazy[u * 2 + 2].mul = (lazy[u * 2 + 2].mul * lazy[u].mul) % mod;
            lazy[u * 2 + 2].add = (lazy[u * 2 + 2].add * lazy[u].mul + lazy[u].add) % mod;

            // 重置当前节点的懒标记
            lazy[u].mul = 1;
            lazy[u].add = 0;
        }
    }

    void updateRange(int u, int s, int e, int l, int r, int add, int mul)
    {
        if(l > e || r < s) return;
        if(l <= s && r >= e)
        {
            tree[u].sum = (tree[u].sum * mul + add * (e - s + 1)) % mod;
            lazy[u].mul = (lazy[u].mul * mul) % mod;
            lazy[u].add = (lazy[u].add * mul + add) % mod;
            return;
        }
        int mid = (s + e) >> 1;
        pushdown(u, s, e, mid);
        updateRange(u * 2 + 1, s, mid, l, r, add, mul);
        updateRange(u * 2 + 2, mid + 1, e, l, r, add, mul);
        tree[u] = merge(tree[u * 2 + 1], tree[u * 2 + 2]);
    }

    int queryRange(int u, int s, int e, int l, int r)
    {
        if(l > e || r < s) return 0;
        if(l <= s && r >= e) return tree[u].sum % mod;
        int mid = (s + e) >> 1;
        pushdown(u, s, e, mid);
        return (queryRange(u * 2 + 1, s, mid, l, r) + queryRange(u * 2 + 2, mid + 1, e, l, r)) % mod;
    }

public:
    SegmentTree(const vector<int>& nums, int p)
    {
        n = nums.size();
        mod = p;
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(nums, 0, 0, n - 1);
    }

    void updateadd(int l, int r, int val)
    {
        updateRange(0, 0, n - 1, l, r, val, 1);
    }

    void updatemul(int l, int r, int val)
    {
        updateRange(0, 0, n - 1, l, r, 0, val);
    }

    int query(int l, int r)
    {
        return queryRange(0, 0, n - 1, l, r);
    }
};

并查集

普通版

1
2
3
4
5
6
7
8
//初始化
for(int i = 1; i <= n; i++) fa[i] = i;
//路径压缩
int find(int x)
{
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];	
}

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int find(int x)
{
	if(x != f[x])
	{
		int t = f[x];
		f[x] = find(f[x]);
		d[x] ^= d[t];
	}
	return f[x];
}
void merge(int x, int y, int z)
{
	int fx = find(x), fy = find(y);
	if(fx != fy) 
	{
		f[fy] = fx;
		d[fy] = d[x] ^ d[y] ^ z;
	}
}

高精度

输入保证为非负整数，且数字没有前导零

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
class bigint
{
private:
	string value;
	
	int cmp(const bigint& other) const
	{
		if(value.length() != other.value.length()) return value.length() < other.value.length() ? -1 : 1;
		return value.compare(other.value);
	}
public:
	bigint(const string& s = "0")
	{
		value = s;
	}
	//加法 
	bigint operator+(const bigint& other) const
	{
		string result;
		int carry = 0;
		int i = value.size() - 1, j = other.value.size() - 1;
		while(i >= 0 || j >= 0 || carry > 0)
		{
			int sum = carry;
			if(i >= 0) sum += value[i--] - '0';
			if(j >= 0) sum += other.value[j--] - '0';
			carry = sum / 10;
			result.push_back(sum % 10 + '0');
		}
		reverse(result.begin(), result.end());
		return bigint(result);
	}
	//减法
	bigint operator-(const bigint& other) const
	{
		string result;
		int borrow = 0;
		int i = value.length() - 1, j = other.value.length() - 1;
		while(i >= 0 || j >= 0)
		{
			int diff = borrow;
			if(i >= 0) diff += value[i--] - '0';
			if(j >= 0) diff -= other.value[j--] - '0';
			if(diff < 0)
			{
				diff += 10;
				borrow = -1; 
			}
			else borrow = 0;
			result.push_back(diff + '0');
 		}
 		reverse(result.begin(), result.end());
 		result.erase(0, result.find_first_not_of('0'));
 		if(result.empty()) result = "0";
 		return bigint(result);
	}
	//乘法
	bigint operator*(const bigint& other) const
	{
		string result(value.length() + other.value.length(), '0');
		for(int i = value.length() - 1; i >= 0; i--)
		{
			int carry = 0;
			for(int j = other.value.length() - 1; j >= 0; j--)
			{
				int temp = (value[i] - '0') * (other.value[j] - '0') + carry + (result[i + j + 1] - '0');
				carry = temp / 10;
				result[i + j + 1] = temp % 10 + '0';//得到的数从1开始 
			}
			result[i] += carry;//进位 
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
	} 
	//除法
	bigint operator/(const bigint& other)const
	{
		if(other.value == "0")  throw runtime_error("Division by zero");
		if(cmp(other) < 0) return bigint("0");
		string result;
		bigint temp("0");
		for(char digit: value)
		{
			temp = temp * bigint("10") + bigint(string(1, digit));
			int count = 0;
			while(temp.cmp(other) >= 0)
			{
				temp = temp - other;
				count++;
			}
			result.push_back(count + '0');
		}
		result.erase(0, result.find_first_not_of('0'));
		if(result.empty()) result = "0";
		return bigint(result);
 	} 
 	friend ostream& operator<<(ostream& os, const bigint& num)
 	{
 		os << num.value;
 		return os;
	 }
};

LCA

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 500010; // 最大节点数
int n, m, s;
// 存边
int to[N * 2], ne[N * 2], head[N], idx; // 无向图，边数需要乘以 2
void add(int u, int v)
{
    to[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}
vector<vector<PII>> query; // 查询列表
int st[N], result[N], fa[N];
// 并查集
int find(int x)
{
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}
void Tarjan(int u)
{
    st[u] = 1; // 标记当前节点为正在访问
    for (int i = head[u]; i != -1; i = ne[i])
    {
        int v = to[i];
        if (st[v]) continue; // 如果子节点已经访问过，跳过
        Tarjan(v);
        merge(v, u); // 合并子节点和当前节点，注意子节点和父节点是谁合并到谁！！！ 
    }
    st[u] = 2; // 标记当前节点为已访问完毕
    // 处理与当前节点相关的查询
    for (auto t : query[u])
    {
        int v = t.first, i = t.second;
        if (st[v] == 2) // 如果查询的另一个节点已经访问完毕
        {
            result[i] = find(v); // LCA 为另一个节点所在集合的根
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(head, -1, sizeof head);
    // n 是节点个数，m 是询问个数，s 是根节点序号
    cin >> n >> m >> s;
    // 初始化 query 和 result
    query.resize(n + 1);
    fill(result, result + m + 1, -1);
    // 存图（无向图）
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    // 添加询问，离线处理
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        query[x].push_back({y, i});
        query[y].push_back({x, i});
    }
    // 预处理并查集
    for (int i = 1; i <= n; i++) fa[i] = i;
    // 调用 Tarjan 算法
    Tarjan(s);
    // 输出查询结果
    for (int i = 1; i <= m; i++)
    {
        cout << result[i] << '\n';
    }
    return 0;
}

倍增法

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010, LOG = 20;
int n, m, s;
vector<int> tree[N];
int dp[N][LOG], dep[N];
//查找深度
void dfs(int u, int p)
{
	dp[u][0] = p;
	for(int i = 1; i < LOG; i++)
		dp[u][i] = dp[dp[u][i - 1]][i - 1];//u的第2^i个父节点等于u的第2^(i-1)个父节点的第2^(i-1)个父节点
	for(auto child: tree[u])
	{
		if(child != p)
		{
			dep[child] = dep[u] + 1;
			dfs(child, u);
		}
	}
} 
int lca(int x, int y)
{
	//让x更深 
	if(dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for(int i = 0; i < LOG; i++)
		if((1 << i) & d) x = dp[x][i];
    //说明x和y的公共祖先是x
	if(x == y) return x;
	//向上倍增
	for(int i = LOG - 1; i >= 0; i--)
	{
		if(dp[x][i] != dp[y][i])
		{
			x = dp[x][i];
			y = dp[y][i];	
		}	
	}
	return dp[x][0]; 
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> s;
	//建树 
	for(int i = 1; i < n; i++) 
	{
		int x, y;
		cin >> x >> y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	//遍历得到深度
	dfs(s, 0); 
	//LCA
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << '\n'; 
	}
	return 0;
}

Kruskal

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 +10;
int n, m, num = 0, ans = 0;
struct Edge
{
	int w;
	int to, pre;
}edge[N];
bool cmp(Edge &x, Edge &y)
{
	return x.w < y.w;
}
int fa[N];
int find(int x)
{
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void merge(int i, int fx, int fy)
{
	fa[fx] = fy;
	num++;
	ans += edge[i].w;
}
void kruskal()
{
	for(int i = 1; i <= m; i++)//依次选权值最小的边
	{
		if(num == n - 1) break;
		int fx = find(edge[i].pre), fy = find(edge[i].to);
		if(fx != fy)
		{
			merge(i, fx, fy);//合并
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edge[i].w = w, edge[i].pre = u, edge[i].to = v;
	}
	sort(edge + 1, edge + m + 1, cmp);//排序
	for(int i = 1; i <= n; i++) fa[i] = i;
	kruskal();
	int flag = 0;
	for(int i = 1; i <= n; i++)
	{
	    if(fa[i] == i) flag++;
	}
	if(flag == 1) cout << ans;
	else cout << "impossible";
	return 0;
}