总体来说蓝桥杯C++ B组省赛还是不难的。

填空题暴力就行了，代码放着跑就行，一般原则就是不超数据范围，不管时间。

我这里的代码不一定是最简单的，复杂度最低的，但是都能通过100%样例。

各题方法列表

这里先把每道题的解题方法列出来，看了方法后尽量自己思考一下

A:dfs

B:模拟

C:数学

D:dfs

E:动态规划

F:两次dfs

G:前缀和/动态规划

H:双向链表+优先队列

I:树上前缀和（lca）

J:树上差分（lca）

A题 日期统计

题目链接：http://oj.ecustacm.cn/problem.php?id=2077

思路：

暴力。先暴力生成8位的日期，再判断该8位日期是否是合法日期。搜索生成日期时，可以剪枝加快搜索速度。

实现代码：

我这里为了省事，把100个数字用输入的方式输入到数组a中了。

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
#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 110;
int a[N], ans;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
unordered_set<int> st;

bool check(int date) {
    if (st.count(date)) return false; // 判断是否重复
    int day = date%100;
    int month = date/100%100;
    if (day < 1 || month > 12 || month < 0) return false;
    if (day <= months[month]) return true;
    return false;
}

// idx表示遍历到数组的下标，len表示当前日期长度，date表示当前日期
void dfs(int idx, int len, int date) {
    if (idx == 100) return;
    if (len == 8) {
        if (check(date)) ++ans;
        st.insert(date);
        return;
    }

    // 当前位作为日期
    if ((len == 0 && a[idx] == 2) ||
        (len == 1 && a[idx] == 0) ||
        (len == 2 && a[idx] == 2) ||
        (len == 3 && a[idx] == 3) ||
        (len == 4 && a[idx] >= 0 && a[idx] <= 1) ||
        (len == 6 && a[idx] >= 0 && a[idx] <= 3) ||
        (len == 5) || (len == 7)) dfs(idx+1, len+1, date*10+a[idx]);

    // 当前位不作为日期
    dfs(idx+1, len, date);
}

int main() {
    for (int i = 0; i < 100; ++i) cin >> a[i];

    dfs(0, 0, 0);
    
    cout << ans << endl;

    return 0;
}

运行之后的正确结果为235。在网站中提交结果时，直接输出235。

B题 01串的熵

题目链接：http://oj.ecustacm.cn/problem.php?id=2078

思路：

其实根据定义可以推出：

设0的个数为$v$，1的个数为$u$，总位数为$N$。其中$v < u, v < N/2$。

可以得出信息熵为:

因此枚举 $v$ 和 $u$ 的取值，再计算对应的信息熵，如果约等于11625907.5798，则得到了答案。

注意：在计算机中浮点数的等于是两者之差绝对值在一个较小的精度范围内

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cmath>

using namespace std;

typedef long double ld;

const int N = 23333333;
const ld ans = 11625907.5798, eps=1e-4;

int main(){
    for(int v = 0; v < N/2; ++v){
        int u = N-v;
        ld res= -1.0*u*u/N*log2(1.0*u/N)-1.0*v*v/N*log2(1.0*v/N);
        if(fabs(res-ans) < eps){
            cout << v << endl;
            break;
        }
    }
    return 0;
}

正确结果为11027421。

C题 冶炼金属

题目链接：https://www.dotcpp.com/oj/problem3150.html

思路：这其实就是一个数学问题，计算最大转换率很简单，就是$\frac{A}{B}$ 向下取整即可（自己思考）

  • 对于最小值：对于 $A、B、minV、maxV$ （$A$为普通金属数量，$B$为特殊金属数量，$minV$ 为最小转换率，$maxV$ 为最大转换率），则有:我们可以考虑一种最极限的方式，A为上诉区间里的最大值，即即但是因为是开区间是不能取等的，因此 $minV$ 还要再加 $1$ 。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>

using namespace std;

int n, a, b, minv = 0, maxv = 0x3f3f3f3f;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        minv = max(minv, a/(b+1));
        maxv = min(maxv, a/b);
    }

    cout << minv + 1 << " " << maxv << endl;
    
    return 0;
}

D题 飞机降落

题目链接：https://www.dotcpp.com/oj/problem3151.html

思路：

从数据范围：$1 \le T \le 10，1 \le N \le 10$ ，即可分析出这道题完全可以用暴力来做。即暴力遍历每种排列组合的情况。

  1. 定义dfs函数参数，我这里定义的是两个参数，第一个参数为当前飞机的编号(p)，第二个参数为当前时间(time)。
  2. 通过这两个参数可以计算：最晚开始降落时间（T[p] + D[p]），如果过它小于当前时间，即该种方案不合理，否则就合理。
  3. 如果合理，就计算降落时间，本机降落结束，其他飞机可以开始降落，即本机降落结束时间就是下一个参数的时间。计算新时间时，要提前判断当前时间time和T[p]的大小关系，应该是这两者大的加上降落时间L[p]。即new_time = max(time, T[p]) + L[p]
  4. 接下来就用循环，再遍历其他没有降落的飞机（是否降落用st数组来表示，如果st[p] = true，表示编号为p的飞机已经降落了）作为下一次降落的飞机。

这里我使用了一个全局变量tempn表示可以降落的飞机数，如果这个数为所有飞机数，即全部飞机都能降落，表示此时满足情况，就修改全局变量flag的值为true，输出YES。

实现代码：

实现代码时要注意回溯

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
#include <iostream>

using namespace std;

const int N = 11;
int t, n, T[N], D[N], L[N], tempn = 1;
bool st[N], flag = false;

void dfs(int p, int time) { // p表示当前飞机的编号, time表示当前时间
    if (time > T[p] + D[p]) return; // 当前飞机已经不满足条件了
    tempn++; // 满足条件的飞机数加一
    if (tempn == n) { // 如果所有飞机都满足条件则则修改结果flag
        flag = true;
        tempn--; // 回溯
        return;
    }
    int ntime = max(time, T[p]) + L[p]; // 计算降落完的时间为新的时间
    for (int i = 0; i < n; ++i) {
        if (!st[i]) {
            st[i] = true;
            dfs(i, ntime);
            st[i] = false; // 回溯
        }
    }
    tempn--; // 回溯
}

void solve() {
    flag = false;

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> T[i] >> D[i] >> L[i];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (flag) break;
            if (i != j) {
                st[i] = true, st[j] = true;
                dfs(j, T[i] + L[i]);
                st[i] =false, st[j] = false; // 回溯
            }
        }
        if (flag) break;
    }

    if (flag) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    cin >> t;
    while (t--) solve();
    
    return 0;
}

E题 接龙数列

题目链接：https://www.dotcpp.com/oj/problem3152.html

思路：

这道题看题目（让求最大，且是一个具体的数）和数据范围（要求复杂度 $O(n\log n)$ ​）都能看出应该是DP问题或者贪心问题。

  1. 确定状态，dp[i]表示以i作为结尾的数 的 最大的 接龙数列 长度
  2. 状态转移方程：对于一个数ixxj(例如1234)，它将会修改dp[j]（dp[4]）的状态，修改状态为：dp[i]+1（dp[1]+1）。这里是要求最大接龙数列长度，因此最终的状态转移方程为：dp[j] = max(dp[j], dp[i]+1)，其中j为当前数的末位数字，i位当前数的首位数字
  3. 每次更新也要一起更新res，即res = max(res, dp[j])，即判断以哪个数作为结尾接龙数列最长
  4. 最终要返回的是最小删除数，这里就可以返回初始数列长度 减去 最大数列长度

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>

using namespace std;

int dp[10], res = 0;

int main() {
    int n;
    string str;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> str;
        int x = str[0] - '0', y = str.back() - '0';
        dp[y] = max(dp[y], dp[x] + 1);
        res = max(dp[y], res);
    }

    cout << n - res << endl;
    
    return 0;
}

F题 岛屿个数

题目链接：https://www.dotcpp.com/oj/problem3153.html

思路：

  1. 先让海水灌进陆地，由样例分析，这里需要用八联通去灌，即新的(x, y)可以朝8个方向走，如果是海水就继续走，完成这一步，所有外海（环外面的海水）都迭代到了。这里更新为2嘛。
    1. 首先用一个比地图大一圈的矩阵来存储这个地图（只需要大一圈就行，根据题目数据范围，可以定义为g[52][52]）
    2. 由于地图外都是海水，所以先所有点都初始化为0
    3. 然后，从(0,0)开始把所有相连的海水都标记为2（第一次DFS）
  2. 将环内的海水（环外的海水已经变成2了，因此目前环内的海水就是还剩下的值为0的地方）变为普通陆地，即遍历整个地图，如果为0，就修改其值为1
  3. 进行普通的岛屿个数计算，如果这步不会，可以参考这道题目：https://leetcode.cn/problems/number-of-islands/description/

实现代码：

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
#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 52;
char g[N][N];
int t, n, m; // 实际范围为 [1, n], 遍历范围为[0, n+1]
int d8[8][2] = {{1, 1}, {1, -1}, {1, 0}, {0, 1}, {0, -1}, {-1, 1}, {-1, -1}, {-1, 0}}; // 八联通
int d4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四联通

bool check1(int x, int y) {
    if (x < 0 || x > n+1 || y < 0 || y > m+1) return false; // 越界
    if (g[x][y] == '0') return true;
    return false;
}

void dfs1(int x, int y) {
    g[x][y] = '2'; // 不是陆地，也不是海水
    for (int i = 0; i < 8; ++i) {
        int nx = x + d8[i][0], ny = y + d8[i][1];
        if (check1(nx, ny)) dfs1(nx, ny);
    }
}

bool check2(int x, int y) {
    if (x < 0 || x > n+1 || y < 0 || y > m+1) return false; // 越界
    if (g[x][y] == '1') return true;
    return false;
}

void dfs2(int x, int y) {
    g[x][y] = '2'; // 不是陆地，也不是海水
    for (int i = 0; i < 4; ++i) {
        int nx = x + d4[i][0], ny = y + d4[i][1];
        if (check2(nx, ny)) dfs2(nx, ny);
    }
}

void solve() {
    // 初始化
    memset(g, '0', sizeof(g));
    int res = 0;

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> g[i][j];
        }
    }

    dfs1(0, 0); // 海水染色

    // 将环内的海水变为普通陆地
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == '0') g[i][j] = '1';
        }
    }

    // 岛屿个数统计
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (check2(i, j)) {
                res++;
                dfs2(i, j);
            }
        }
    }

    cout << res << endl;
}

int main() {
    cin >> t;
    while (t--) solve();

    return 0;
}

G题 子串简写

题目链接：https://www.dotcpp.com/oj/problem3154.html

思路：
这道题的数据范围一看就知道不能暴力去做（暴力的时间复杂的大概是 $O(n^2)$ ，但是数据范围要求的时间复杂度为 $O(n)$ ，因此就要想想别的算法，因为是返回一个具体的数值。最终想到了前缀和（其实也可以理解为DP）。

  1. 如果字符串第i位等于a字符，cnt[i] = cnt[i-1]+1否则cnt[i] = cnt[i-1]。即统计i位之前有多少个合法开头。
  2. 如果过遇到字符串第i位等于b字符，ans += cnt[i-k+1]。即统计k位之前有多少个合法的开头，有多少合法开头就可以构成多少合法子串。

上诉代码能看懂的话，就能看懂下面的代码，因为是简写，应该不难理解。

注意结果要开long long

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int k, n;
long long ans, cnt;
string str;
char a, b;

int main() {
    cin >> k >> str >> a >> b;

    int n = str.size();
    for (int i = 0; i < n; ++i) {
        if (i-k+1 >= 0 && str[i-k+1] == a) cnt++;
        if (str[i] == b) ans += cnt;
    }

    cout << ans << endl;

    return 0;
}

H题 整数删除

题目链接：https://www.dotcpp.com/oj/problem3155.html

思路：

  • 根据题目的数据范围，得知这道题的时间复杂度为$O(n \log n)$，因此根本不能通过遍历的方式来找最小值及其位置，而且每次操作都会修改值和下标，使用排序的方法肯定是不行的。

  • 因此需要考虑用数据结构来动态维护，这里就想到了用优先队列实现小根堆的方式来维护最小值和最小值的下标。

  • 其次更新数列很明显需要使用链表，并且需要同时修改左右两个数，因此需要使用双向链表。

  • 最后为了能够快速地索引元素，可以使用数组来实现双向链表（不使用传统结构体的方式），具体可以参看文章：文章。其中idx是每一个链表节点的固定编号，节点增删都不影响这个编号，可以通过这个编号快速查询节点。

实现代码：

注意：

  1. 数据范围要开long long

  2. 我交了一次代码只有81分，没有通过全部样例，但是方法基本已经最简单了，因此我尝试了用scanf和printf来输入输出，看得出时间会快一点，但是还是81分

  3. 我原本的代码中大概35行为：

    1
    int v = p.first, idx = p.second;

    即我为了方便，提前提取了first和second的值。后面我直接使用，即如下代码，即可通过全部样例。

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
#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

const int N = 5e5+5;

int n, k, l[N], r[N];
ll e[N];
priority_queue<pli, vector<pli>, greater<pli> > q; // 堆中每个元素为：{节点值， 节点下标}

void del(int idx) {
    e[l[idx]] += e[idx], e[r[idx]] += e[idx]; // 修改值
    r[l[idx]] = r[idx], l[r[idx]] = l[idx]; // 删除节点
}

int main() {
    scanf("%d%d", &n, &k);
    r[0] = 1, l[n+1] = n; // 节点下标为0表示左端点，下标为n+1为右端点，真实节点下标范围为[1, n]，因此左端点的右节点编号为1，右端点的左节点编号为n
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &e[i]); // 输入节点值，这里是线性的，因此下标直接用i
        l[i] = i-1, r[i] = i+1; // 更新链表两端关系，i的左边元素的下标一定为i-1，右边元素一定为i+1

        q.push({e[i], i}); // 将元素添加到堆中维护
    }

    while (k--) {
        // 取出堆中的最小元素
        auto p = q.top();
        q.pop();

        if (e[p.second] != p.first) { // p.first不一定是真实值，e[p.second]是真实值，如果两者
            q.push({e[p.second], p.second}), k++; // 并没有实际处理元素，因此 k 加回去
        } else { // 如果过两者值不等，说明链表中的真实值和堆中值不同了，重新更新堆中的值
            del(p.second);
        }
    }

    // 遍历链表中剩下的元素，即结果
    for (int i = r[0]; i != n+1; i = r[i]) 
        printf("%lld ", e[i]);

    return 0;
}

I题 景区导游

题目链接：https://www.dotcpp.com/oj/problem3156.html

思路：

节点数最多为1e5，结合「树上最短距离」，可以想到用LCA求树上最短距离。

树上距离的一般求法为树上前缀和，如果不会可以参看我的另一篇文章：树上前缀和及树上差分中的树上前缀和内容。

对于x、y、z这样的访问序列，跳过y，其实就是：总花费-花费(x,y)-花费(y,z)+花费(x,z)

特殊地：

跳过第一个(x)：总花费-花费(x,y)

跳过最后一个(y)：总花费-花费（x,y）

实现代码：

这里存树，其实就是存图，如果不会可以参看我的另一篇文章：链式向前星
这里使用倍增法求LCA，如果不会，可以参看我的另一篇文章：最近公共祖先(LCA)

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
#include <iostream>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100005, M=N*2;

int n, m;
int h[N], e[M], w[M], ne[M], idx; // 存树
int depth[N], fa[N][18]; // depth记录节点深度，fa记录向上跳的节点
int q[N]; // 队列，用于宽度优先搜索
ll dist[N]; // 记录节点与根节点的距离
int query[N]; // 记录浏览顺序
ll sum = 0; // 不跳过的总花费

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int root) {
	memset(depth, INF, sizeof(depth));
	depth[0] = 0, depth[root] = 1;
	int hh = 0, tt = 0;
	q[0] = root;

	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (depth[j] > depth[t] + 1) {
				dist[j] = dist[t] + w[i];
				depth[j] = depth[t] + 1;
				q[++tt] = j;

				fa[j][0] = t;
				for (int k = 1; k <= 17; ++k) {
					fa[j][k] = fa[fa[j][k-1]][k-1];
				}
			}
			
		}
	}
}

int lca(int a, int b) {
	// 跳到同一层
	if (depth[a] < depth[b]) swap(a, b);
	for (int k = 17; k >= 0; --k)
		if (depth[fa[a][k]] >= depth[b])
			a = fa[a][k];
	if (a == b) return a;

	// 一起往上跳
	for (int k = 17; k >= 0; --k) 
		if (fa[a][k] != fa[b][k]) {
			a = fa[a][k];
			b = fa[b][k];
		}
	return fa[a][0];
}

ll cost(int a, int b) {
	int anc = lca(query[a], query[b]);
	return dist[query[a]] + dist[query[b]] - 2*dist[anc];
}

int main() {
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	int a, b, c;
	for (int i = 0; i < n-1; ++i) {
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}

	bfs(1); // 随便选个编号为1的节点做根节点

	// 输入浏览顺序
	for (int i = 1; i <= m; ++i) cin >> query[i];
	// 计算总花费
	for (int i = 2; i <= m; ++i) sum += cost(i, i-1);
	// 跳过第一个
	cout << sum - cost(1, 2) << " ";
	// 跳过第i个
	for (int i = 2; i < m; ++i) 
		cout << sum - cost(i, i+1) - cost(i, i-1) + cost(i-1, i+1) << " ";
	// 跳过最后一个
	cout << sum - cost(m, m-1);

	return 0;
}

J题 砍树

题目链接：https://www.dotcpp.com/oj/problem3157.html

思路：

这道题其实就是需要减去公共边。对于样例，想要隔离3 6，就是要砍掉3->6(3->2->5->6)的某一条边；想要隔离4 5就是要砍掉4->5（4->3->2->5）的一条边。但是只能砍一条边，因此这一条边一定要死这两条路的公共边。通过观察，可以发现可以减去2->5或者3->2。但是2->5的编号大，于是返回2->5的编号4。

于是问题转化为：求m个通路的公共边。

求m个通路的公共边可以考虑加边权，例如，样例中的3->6,通路为3->2->5->6，于是给3->2、2->5、5->6这三个边的边权加一。这样当求完m个通路时，再去遍历每条边的边权，如果边权为m，则该边可以作为答案（可能有多个边，要返回编号最大的）。

从上面的思路总可以得出暴力做法，就是通过DFS或者BFS暴力遍历通路，然后通路的每条边的边权加一。但是，这样暴力一定会超时。这样的操作其实是对一个区间内的点都进行相同的加一操作，很容易能够想到差分（对区间的两个端点进行操作，即可操作整个区间）。于是最终转换为树上差分的问题。

如果不会树上差分可以参看我的另一篇文章：树上前缀和及树上差分中的树上差分内容。

实现代码：

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5+5, M = 2*N;

int n, m;
int h[N], e[M], ne[M], idx; // 存图
int depth[N], fa[N][16]; // depth为深度，fa为父节点
int q[N]; // 队列
map<pii, int> id; // 记录边的编号
int d[N]; // 差分数组
int ans = -1; // 最终结果编号,没有答案返回-1

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int root) {
	memset(depth, INF, sizeof(depth));
	depth[0] = 0, depth[root] = 1;
	int hh = 0, tt = 0;
	q[0] = root;

	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (depth[j] > depth[t] + 1) {
				depth[j] = depth[t] + 1;
				q[++tt] = j;

				fa[j][0] = t;
				for (int k = 1; k <= 15; ++k) fa[j][k] = fa[fa[j][k-1]][k-1];
			}
		}
	}
}

int lca(int a, int b) {
	// 跳到同一层
	if (depth[a] < depth[b]) swap(a, b);
	for (int k = 15; k >= 0; --k)
		if (depth[fa[a][k]] >= depth[b])
			a = fa[a][k];
	if (a == b) return a;

	// 一起往上跳
	for (int k = 15; k >= 0; --k)
		if (fa[a][k] != fa[b][k]) {
			a = fa[a][k];
			b = fa[b][k];
		}
	return fa[a][0];
}

int get_sum(int u) {
	int sum = d[u];
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (depth[j] == depth[u] + 1) {
			int res = get_sum(j);
			sum += res;
		}
	}
	if (sum == m && ans < id[{fa[u][0], u}])
		ans = id[{fa[u][0], u}];
	return sum;
}

int main() {
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a); // 无向边
		id[{a, b}] = i; id[{b, a}] = i; // 记录边的编号
	}

    int root = 1; // 选择节点编号为1的节点作为根节点

	bfs(root);

	for (int i = 0;  i < m; ++i) {
		int a, b;
		cin >> a >> b;
		d[a] ++, d[b] ++;
		d[lca(a, b)] -= 2;
	}

	get_sum(root);

	cout << ans << endl;

	return 0;
}