目前除 B、F題未補(bǔ)，其余題均已更完，經(jīng)非官方數(shù)據(jù)測(cè)試均可AC。歡迎交流

試題 A. 日期統(tǒng)計(jì)

1.題目描述

??小藍(lán)現(xiàn)在有一個(gè)長(zhǎng)度為 100 的數(shù)組，數(shù)組中的每個(gè)元素的值都在 0 到 9 的
范圍之內(nèi)。數(shù)組中的元素從左至右如下所示：

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

現(xiàn)在他想要從這個(gè)數(shù)組中尋找一些滿足以下條件的子序列：

• 1. 子序列的長(zhǎng)度為 $8$；
• 2. . 這個(gè)子序列可以按照下標(biāo)順序組成一個(gè) $yyyymmdd$ 格式的日期，并且
     要求這個(gè)日期是 $2023$ 年中的某一天的日期，例如 $20230902，20231223$。
     $yyyy$ 表示年份，$mm$ 表示月份，$dd$ 表示天數(shù)，當(dāng)月份或者天數(shù)的長(zhǎng)度只
     有一位時(shí)需要一個(gè)前導(dǎo)零補(bǔ)充。

??請(qǐng)你幫小藍(lán)計(jì)算下按上述條件一共能找到多少個(gè)不同 的 2023 年的日期。
對(duì)于相同的日期你只需要統(tǒng)計(jì)一次即可。

2.解題思路

??考慮八層循環(huán)枚舉一下，中間需要進(jìn)行減枝加快搜索步驟，不建議寫 dfs，不然就像我一樣在考場(chǎng)寫爛，注意答案需要去重，答案為235。

3.模板代碼

??暫更

試題 B.01 串的熵

1.題目描述

??沒學(xué)過數(shù)學(xué)，暫更

2.解題思路

3.模板代碼

試題 C. 冶煉金屬

1.題目描述

??小藍(lán)有一個(gè)神奇的爐子用于將普通金屬 $O$ 冶煉成為一種特殊金屬 $X$。這個(gè)
爐子有一個(gè)稱作轉(zhuǎn)換率的屬性 $V$，$V$ 是一個(gè)正整數(shù)，這意味著消耗 $V$ 個(gè)普通金
屬 $O$ 恰好可以冶煉出一個(gè)特殊金屬 $X$，當(dāng)普通金屬 $O$ 的數(shù)目不足 $V$ 時(shí)，無法
繼續(xù)冶煉。
??現(xiàn)在給出了 $N$ 條冶煉記錄，每條記錄中包含兩個(gè)整數(shù) $A$ 和 $B$，這表示本次投入了 $A$ 個(gè)普通金屬 $O$，最終冶煉出了 $B$ 個(gè)特殊金屬 $X$。每條記錄都是獨(dú)立
的，這意味著上一次沒消耗完的普通金屬 $O$ 不會(huì)累加到下一次的冶煉當(dāng)中。
??根據(jù)這 $N$ 條冶煉記錄，請(qǐng)你推測(cè)出轉(zhuǎn)換率 $V$ 的最小值和最大值分別可能是多少，題目保證評(píng)測(cè)數(shù)據(jù)不存在無解的情況。

2. 解題思路

??如果看過樣例的話，顯然答案兩個(gè)上下界都是可以直接二分出來的。因?yàn)槭阶拥慕Y(jié)構(gòu)都是 $\frac{A}{C}=B$。$A$ 是不變的，我們先考慮二分求最小的 $C$，因?yàn)樾枰ＷC所有式子的 $B$ 都不變，如果 $C$ 太小，顯然會(huì)有某一組的 $B$ 增大，所以需要保證每一組都符合a[i]/x <= b[i]。反過來考慮求最大的 $C$, 如果 $C$ 太大，顯然會(huì)有某一組的 $B$ 變小，需要保證每一組都符合 a[i]/x >= B。

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n;
int a[N], b[N];
bool check(LL x) {
	for (int i = 1; i <= n; ++i) {
		if (a[i] / x > b[i]) return false;
	}
	return true;
}
bool check2(LL x) {
	for (int i = 1; i <= n; ++i) {
		if (a[i] / x < b[i]) return false;
	}
	return true;
}
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	LL l = 1, r = 1e9;
	while (l < r) {
		LL mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	int s = r;
	l = 1, r = 1e9;
	while (l < r) {
		LL mid = l + r + 1 >> 1;
		if (check2(mid)) l = mid;
		else r = mid - 1;
	}
	cout << s << " " << r << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

試題 D. 飛機(jī)降落

1.題目描述

?? $N$ 架飛機(jī)準(zhǔn)備降落到某個(gè)只有一條跑道的機(jī)場(chǎng)。其中第 $i$ 架飛機(jī)在 $Ti$ 時(shí)刻到達(dá)機(jī)場(chǎng)上空，到達(dá)時(shí)它的剩余油料還可以繼續(xù)盤旋 $Di$ 個(gè)單位時(shí)間，即它最早
可以于 $Ti$ 時(shí)刻開始降落，最晚可以于 $Ti+Di$ 時(shí)刻開始降落。降落過程需要 $Li$
個(gè)單位時(shí)間。
??一架飛機(jī)降落完畢時(shí)，另一架飛機(jī)可以立即在同一時(shí)刻開始降落，但是不
能在前一架飛機(jī)完成降落前開始降落。
??請(qǐng)你判斷 $N$ 架飛機(jī)是否可以全部安全降落。

2. 解題思路

?? 看 $N$ 最大為10，T最大也為10，考慮全排列枚舉所有的降落情況，只要有一種符合的情況即可，大概計(jì)算一下復(fù)雜度為$10!\times 10\times 10$ 等于3e8，理論可過 。

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;


int n;
int a[N], b[N], c[N];
void solve()
{
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];
	std::vector<int> d(n);
	auto check = [&]() {
		int v = 0;
		for (int i = 0; i < n; ++i) {
			int x = d[i];
			if (i == 0) {
				v = a[x] + c[x];
			} else {
				if (a[x] + b[x] < v) return false;
				v = max(v, a[x]) + c[x];
			}
		}
		return true;
	};
	iota(all(d), 0);
	bool f = false;
	do {
		if (check()) {
			f = true;
			break;
		}
	} while (next_permutation(all(d)));
	if (f) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

試題 E. 接龍數(shù)列

1.題目描述

?? 對(duì)于一個(gè)長(zhǎng)度為 $K$ 的整數(shù)數(shù)列：$A_1,A_2,...,A_K$，我們稱之為接龍數(shù)列當(dāng)且僅當(dāng) $A_i$ 的首位數(shù)字恰好等于 $A_{i?1}$ 的末位數(shù)字 $(2\le i\le K)$。
?? 例如 $12,23,35,56,61,11$ 是接龍數(shù)列；$12,23,34,56$ 不是接龍數(shù)列，因?yàn)?$56$ 的首位數(shù)字不等于 $34$ 的末位數(shù)字。所有長(zhǎng)度為 $1$ 的整數(shù)數(shù)列都是接龍數(shù)列。
?? 現(xiàn)在給定一個(gè)長(zhǎng)度為 $N$ 的數(shù)列 $A_1,A_2,...,A_N$，請(qǐng)你計(jì)算最少從中刪除多少個(gè)數(shù)，可以使剩下的序列是接龍序列？

2. 解題思路

?? 考場(chǎng)讀完題的時(shí)候感覺有點(diǎn)奇怪，發(fā)現(xiàn)思路還是比較簡(jiǎn)單的。首先一個(gè)數(shù)我們只需要關(guān)注其首位數(shù)字和末位數(shù)字，定以 $f[i]$ 為以數(shù)字 $i$ 結(jié)尾的最長(zhǎng)接龍序列的長(zhǎng)度，$i$ 的范圍是 $[0,9]$。對(duì)于每個(gè)數(shù)字設(shè)其首位數(shù)字為 $a$ ，末尾數(shù)字為 $b$，則有轉(zhuǎn)移方程：
$$f[b]=max(f[b],f[a]+1)$$
?? 最后在 $f[0]、f[1]...f[9]$ 取一個(gè)最大值 $ans$，答案則為 $n?ans$。

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n;
int a[N], b[N];
int f[10];
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		b[i] = x % 10;
		string s = to_string(x);
		a[i] = s[0] - '0';
	}
	for (int i = 1; i <= n; ++i) {
		f[b[i]] = max(f[b[i]], f[a[i]] + 1);
	}
	int ans = 0;
	for (int i = 0; i <= 9; ++i) ans = max(ans, f[i]);
	cout << n - ans << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

試題 F. 島嶼個(gè)數(shù)

1.題目描述

暫更，感覺不好寫

2. 解題思路

3.模板代碼

試題 G. 子串簡(jiǎn)寫

1.題目描述

?? 程序猿圈子里正在流行一種很新的簡(jiǎn)寫方法：對(duì)于一個(gè)字符串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長(zhǎng)度代替。例如 $internation?alization$ 簡(jiǎn)寫成 $i18n$，$Kubernetes$ （注意連字符不是字符串的一部分）簡(jiǎn)寫成 $K8s,Lanqiao$ 簡(jiǎn)寫成 $L5o$等。
?? 在本題中，我們規(guī)定長(zhǎng)度大于等于 $K$ 的字符串都可以采用這種簡(jiǎn)寫方法（長(zhǎng)度小于 $K$ 的字符串不配使用這種簡(jiǎn)寫）。
?? 給定一個(gè)字符串 $S$ 和兩個(gè)字符 $c1$ 和 $c2$，請(qǐng)你計(jì)算 $S$ 有多少個(gè)以 $c1$ 開頭 $c2$ 結(jié)尾的子串可以采用這種簡(jiǎn)寫？

2. 解題思路

?? 這道題放在 G 題感覺更奇怪了，一道前綴和模板題。假設(shè)下標(biāo)為 $i$ 的字符為 $c1$，那我們只需要統(tǒng)計(jì)在區(qū)間 $[i+k?1,n]$有多少個(gè) $c2$ 即可，前綴和預(yù)處理一下 $c2$ 字符，直接累加答案即可，注意答案會(huì)爆int，復(fù)雜度 $O(n)$

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 500010;

int k;
string s;
char c1, c2;
int a[N];
void solve()
{
	cin >> k >> s >> c1 >> c2;
	int n = s.size();
	s = '?' + s;
	for (int i = 1; i <= n; ++i) {
		a[i] = (s[i] == c2);
		a[i] += a[i - 1];
	}
	LL ans = 0;
	for (int i = 1; i + k - 2 < n; ++i) {
		if (s[i] == c1) ans += a[n] - a[i + k - 2];
	}
	cout << ans << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

試題 H.整數(shù)刪除

1.題目描述

?? 給定一個(gè)長(zhǎng)度為 $N$ 的整數(shù)數(shù)列：$A_1,A_2,...,A_N$。你要重復(fù)以下操作 $K$ 次：
?? 每次選擇數(shù)列中最小的整數(shù)（如果最小值不止一個(gè)，選擇最靠前的），將其刪除。并把與它相鄰的整數(shù)加上被刪除的數(shù)值。
?? 輸出 $K$ 次操作后的序列。

2. 解題思路

?? 感覺是比較典的題目，用優(yōu)先隊(duì)列維護(hù)，存入值和下標(biāo)，再用一個(gè)數(shù)組cnt累計(jì)每個(gè)下標(biāo)增加的和，當(dāng)彈出最小的值下標(biāo)為 i 時(shí)，如果此時(shí)cnt[i]不等于0，說明它實(shí)際的值需要加上cnt[i]，我們將其增加后再放回優(yōu)先對(duì)列，注意需要清空cnt[i]。如果此時(shí)cnt[i]等于0，那我們就成功彈出當(dāng)前最小元素，這時(shí)需要將其前一個(gè)元素和后一個(gè)元素值增加，我們需要模擬鏈表去記錄每個(gè)元素的前后元素是誰，pre[i]表示下標(biāo)為i的上一個(gè)元素是誰，ne[i]表示下標(biāo)為 i 的下一個(gè)元素是誰，直到堆的元素個(gè)數(shù)只剩n-k時(shí)結(jié)束循環(huán)。不難想象，堆元素的出入次數(shù)是線性的。

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 500010;

int n, k;
int pre[N], ne[N];
LL cnt[N];
void solve()
{
	cin >> n >> k;
	priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>> >q;
	for (int i = 1; i <= n; ++i) {
		LL v;
		cin >> v;
		q.push({v, i});
		pre[i] = i - 1;
		ne[i] = i + 1;
	}
	int g = n - k;
	while (q.size() > g) {
		auto p = q.top(); q.pop();
		LL v = p.first, ix = p.second;
		if (cnt[ix]) {
			q.push({v + cnt[ix], ix});
			cnt[ix] = 0;
		} else {
			int l = pre[ix], r = ne[ix];
			cnt[l] += v;
			cnt[r] += v;
			ne[l] = r;
			pre[r] = l;
		}
	}
	std::vector<LL> a(n + 1);
	for (int i = 0; i < g; ++i) {
		auto p = q.top(); q.pop();
		a[p.second] = p.first + cnt[p.second];
	}
	for (int i = 1; i <= n; ++i) {
		if (a[i]) cout << a[i] << " ";
	}
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

試題 I. 景區(qū)旅游

1.題目描述

?? 某景區(qū)一共有 $N$ 個(gè)景點(diǎn)，編號(hào) $1$ 到 $N$。景點(diǎn)之間共有 $N?1$ 條雙向的擺渡車線路相連，形成一棵樹狀結(jié)構(gòu)。在景點(diǎn)之間往返只能通過這些擺渡車進(jìn)行，需要花費(fèi)一定的時(shí)間。
?? 小明是這個(gè)景區(qū)的資深導(dǎo)游，他每天都要按固定順序帶客人游覽其中 $K$ 個(gè)景點(diǎn)：$A_1,A_2,...,A_K$。今天由于時(shí)間原因，小明決定跳過其中一個(gè)景點(diǎn)，只帶游客按順序游覽其中 $K?1$ 個(gè)景點(diǎn)。具體來說，如果小明選擇跳過 $A_i$，那么他會(huì)按順序帶游客游覽 $A_1,A_2,...,A_{i?1},A_{i+1},...,A_K,(1\le i\le K)$。
?? 請(qǐng)你對(duì)任意一個(gè) $Ai$，計(jì)算如果跳過這個(gè)景點(diǎn)，小明需要花費(fèi)多少時(shí)間在景點(diǎn)之間的擺渡車上？

2. 解題思路

?? $LCA$ 模板題（問題是比賽寫不出板子呢），首先肯定需要考慮求樹上任意兩點(diǎn)的距離。設(shè)點(diǎn) $u,v$ 的最近公共祖先為 $z$，定義$f[i]$ 為點(diǎn) $i$ 到根節(jié)點(diǎn)的距離，那么則有公式:
$$dist(u,v)=f[u]+f[v]?2?f[z]$$
?? 先求出不跳過任何的點(diǎn)時(shí)需要走的距離為ans以及任意相鄰兩個(gè)跳點(diǎn)的距離。假設(shè)我們跳過四個(gè)點(diǎn)分別為 $a,b,c,d$。當(dāng)跳過的點(diǎn)為 $a$ 時(shí)，我們只需要用ans減去$a$到$b$的距離，當(dāng)跳過的點(diǎn)為 $d$ 時(shí)，我們只需要用ans減去 $c$ 到 $d$ 的距離，這是首尾兩個(gè)點(diǎn)的情況。
?? 那么當(dāng)跳過的點(diǎn)為中間點(diǎn)呢？比如我們跳過的是 $b$，那么則需要用ans減去$a$到$b$以及$b$到$c$的距離，并且還需要加上$a$到$c$的距離，其余的中間點(diǎn)處理同理。

3.模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s)
#define SZ(s) ((int)s.size())
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int  mod = 1000000007;
const int N = 200010;

int n, m;
std::vector<pair<int, LL>> e[N];
int depth[N], fa[N][32];
LL f[N];
int root;
void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (auto [j, c] : e[t]) {
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 20; k++) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}
void dfs(int u, int fa) {
    for (auto [v, c] : e[u]) {
        if (v == fa) continue;
        f[v] = f[u] + c;
        dfs(v, u);
    }
}
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; k >= 0; k--) {
        if (depth[fa[a][k]] >= depth[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 20; k >= 0; --k) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
LL calc(int u, int v) {
    int z = lca(u, v);
    return f[u] + f[v] - 2 * f[z];
}
void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v , c;
        cin >> u >> v >> c;
        e[u].push_back({v, c});
        e[v].push_back({u, c});
    }
    bfs(1);
    dfs(1, -1);
    std::vector<LL> g(m + 1);
    for (int i = 1; i <= m; ++i) cin >> g[i];
    LL ans = 0;
    for (int i = 1; i < m; ++i) {
        ans += calc(g[i], g[i + 1]);
    }
    for (int i = 1; i <= m; ++i) {
        if (i == 1) cout << ans - calc(g[i], g[i + 1]) << " ";
        else if (i == m) cout << ans - calc(g[i - 1], g[i]) << " ";
        else {
            LL res = ans - calc(g[i], g[i + 1]) - calc(g[i - 1], g[i]) + calc(g[i - 1], g[i + 1]);
            cout << res << " ";
        }
    }
}
signed main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

試題 J. 砍樹

1.題目描述

?? 給定一棵由 $n$ 個(gè)結(jié)點(diǎn)組成的樹以及 $m$ 個(gè)不重復(fù)的無序數(shù)對(duì) $(a1,b1),(a_2,b_2),...,(a_m,b_m)$，其中 $ai$ 互不相同，$b_i$ 互不相同，$a_i,b_j(1\le i,j\le m)$。
?? 小明想知道是否能夠選擇一條樹上的邊砍斷，使得對(duì)于每個(gè) $(ai,bi)$ 滿足 $ai$和 $bi$ 不連通，如果可以則輸出應(yīng)該斷掉的邊的編號(hào)（編號(hào)按輸入順序從 $1$ 開始），否則輸出 $?1$。

2. 解題思路

?? 又是 $LCA$ 模板題啊，但我之前沒做過（反正也寫不出 $LCA$）?？紤]一對(duì)無序數(shù)對(duì)的點(diǎn) $x$ 和 $y$ ，如果我們砍掉某條邊可以讓這兩個(gè)點(diǎn)不連通，那么這條邊一定是從 $x$ 到 $y$ 路徑上的一點(diǎn)，我們可以讓從 $x$ 到 $y$ 路徑的邊權(quán)值都加1。這個(gè)操作我們可以使用樹上差分。 對(duì)于 $m$ 個(gè)無序數(shù)對(duì)我們都如此操作，最后如果某條邊的權(quán)值為 $m$ 則說明它符合條件，我們選出符合條件編號(hào)最大的那條邊就是答案，如果沒有權(quán)值為 $m$ 的邊則說明無解。文章來源地址http://www.zghlxwxcb.cn/news/detail-411896.html

3. 模板代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n, m;
std::vector<int> e[N];
int depth[N], fa[N][32];
int f[N];
int root;
int ans;
map<PII, int> mp;
void bfs(int root)
{
	ms(depth, 0x3f);
	depth[0] = 0, depth[root] = 1;
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
		for (int j : e[t]) {
			if (depth[j] > depth[t] + 1) {
				depth[j] = depth[t] + 1;
				q.push(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 dfs(int u, int fa) {
	int res = f[u];
	for (auto v : e[u]) {
		if (v == fa) continue;
		int g = dfs(v, u);
		if (g == m) {
			ans = max(ans, mp[ {v, u}]);
		}
		res += g;
	}
	return res;
}
void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		mp[ {u, v}] = mp[ {v, u}] = i + 1;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	bfs(1);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		int z = lca(u, v);
		f[u]++;
		f[v]++;
		f[z] -= 2;
	}
	dfs(1, -1);
	cout << (ans == 0 ? -1 : ans) << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽（C/C++B組）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！