2023藍(lán)橋C/C++B組省賽

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

題目描述

【問題描述】
小藍(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ì)一次即可。

枚舉

用八重循環(huán)直接枚舉每一位數(shù)字， 題目中的日期序列有很多限制， 如前四位必須是2023， 又比如月份只能以0或1開頭等等。利用這些限制能大大降低運(yùn)行時(shí)間， 實(shí)測(cè)只要限制了前四位， 基本是瞬間跑出結(jié)果。

注意需要用哈希表去重。

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
set<int> res;

void check(int m, int d) {
    if (m < 1 || m > 12 || d < 1 || d > days[m]) return;
    res.insert(m * 100 + d);
}

int main () {
    int ns[100];
    for (int & n : ns) cin >> n;
    for (int a = 0; a < 100; a ++) {
        if (ns[a] != 2) continue;
        for (int b = a + 1; b < 100; b ++) {
            if (ns[b] != 0) continue;
            for (int c = b + 1; c < 100; c ++) {
                if (ns[c] != 2) continue;
                for (int d = c + 1; d < 100; d ++) {
                    if (ns[d] != 3) continue;

                    for (int i = d + 1; i < 100; i ++)
                        for (int j = i + 1; j < 100; j ++)
                            for (int k = j + 1; k < 100; k ++)
                                for (int l = k + 1; l < 100; l ++)
                                    check(ns[i] * 10 + ns[j], ns[k] * 10 + ns[l]);
                }
            }
        }
    }
    cout << res.size() << endl;
    return 0;
}
//in: 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
//out: 235

試題B: 01 串的熵

題目描述

對(duì)于一個(gè)長(zhǎng)度為n 的01 串$S=x_1{x}_2{x}_3...x_n$，香農(nóng)信息熵的定義為$H(S)=?{\sum }_1^{n}p(x_i){\log }_2(p(x_i))$，其中$p(0),p(1)$ 表示在這個(gè)01 串中0 和1 出現(xiàn)的占比。

比如，對(duì)于S = 100 來說，信息熵$H(S)=?\frac{1}{3}{\log }_2(\frac{1}{3})?\frac{2}{3}{\log }_2(\frac{2}{3})?\frac{2}{3}{\log }_2(\frac{2}{3})=1.3083$。對(duì)于一個(gè)長(zhǎng)度為23333333 的01 串，如果其信息熵為11625907.5798，且0 出現(xiàn)次數(shù)比1 少，那么這個(gè)01 串中0 出現(xiàn)了多少次？

枚舉|模擬

設(shè)01字符串S長(zhǎng)度為n, 0的個(gè)數(shù)為x。

則$p(0)=\frac{x}{n},p(1)=\frac{n?x}{n}$.

$H(S)=?{\sum }_1^{n}p(x_i){\log }_2(p(x_i))=?(xp(0){\log }_2(p(0))+(n?x)p(1){\log }_2(p(1)))$

在已知n, x時(shí)， 計(jì)算H是$O(1)$的， 所以只需要枚舉x即可。

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll H = 116259075798;
const ll N = 23333333;

bool check(ll x) {
    double p0 = x * 1.0 / N, p1 = 1 - p0;
    ll h = 10000ll * (x * p0 * log2(p0) + (N - x) * p1 * log2(p1));
    return h + H == 0;
}

int main () {
    for (int x = 1; x <= N / 2; x ++) {
        if (check(x)) cout << x << endl;
    }
    return 0;
}
//out: 11027421

試題C: 冶煉金屬

題意描述

小藍(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ù)不存在無解的情況。

取交集

對(duì)于每一條記錄， 都可以求出轉(zhuǎn)換率V的一個(gè)取值范圍。 V必須滿足所有記錄求出的取值范圍， 所以只需要對(duì)N個(gè)區(qū)間求交集即可, 也就是右邊界取所有右邊界的最小值， 左邊界取所有左邊界的最大值。。

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n; cin >> n;
    int mn = -1, mx = 1e9;
    while (n --) {
        int a, b; cin >> a >> b;
        int l = a / (b + 1) + 1, r = a / b;
        mn = max(mn, l), mx = min(mx, r);
    }
    cout << mn << " " << mx << endl;
    return 0;
}

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

題意描述

N 架飛機(jī)準(zhǔn)備降落到某個(gè)只有一條跑道的機(jī)場(chǎng)。其中第i 架飛機(jī)在$T_i$ 時(shí)刻到達(dá)機(jī)場(chǎng)上空，到達(dá)時(shí)它的剩余油料還可以繼續(xù)盤旋$D_i$ 個(gè)單位時(shí)間，即它最早可以于$T_i$ 時(shí)刻開始降落，最晚可以于$T_i+D_i$ 時(shí)刻開始降落。降落過程需要$L_i$
個(gè)單位時(shí)間。

一架飛機(jī)降落完畢時(shí)，另一架飛機(jī)可以立即在同一時(shí)刻開始降落，但是不能在前一架飛機(jī)完成降落前開始降落。

請(qǐng)你判斷N 架飛機(jī)是否可以全部安全降落。

DFS+剪枝， 懶得寫

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

題意描述

對(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 ≤ i ≤ K)。

例如$12,23,35,56,61,11$ 是接龍數(shù)列；$12,23,34,56$ 不是接龍數(shù)列，因?yàn)?6的首位數(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ù)，可以使剩下的序列是接龍序列？

DP

要求使得數(shù)列變成接龍數(shù)列的最少刪除個(gè)數(shù)， 相當(dāng)于求該數(shù)列的最長(zhǎng)接龍子數(shù)列的長(zhǎng)度， 用總長(zhǎng)度減去最長(zhǎng)接龍長(zhǎng)度即為最少刪除個(gè)數(shù)。

定義$dp[i][j]$為前i個(gè)數(shù)中， 以數(shù)字j結(jié)尾的最長(zhǎng)接龍數(shù)列的長(zhǎng)度。

設(shè)第i個(gè)數(shù)的首位數(shù)字是a， 末位數(shù)字是b。 則$dp[i]$中相對(duì)于$dp[i?1]$可能發(fā)生變化的只有$dp[i][b]$, 因?yàn)榈趇個(gè)數(shù)可能加到一個(gè)以a結(jié)尾的接龍數(shù)列中， 使得這個(gè)接龍數(shù)列長(zhǎng)度加1并且結(jié)尾數(shù)字變成b.

所以狀態(tài)轉(zhuǎn)移方程為dp[i][b] = max(dp[i - 1][b], dp[i - 1][a] + 1)

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
int dp[10];

int main () {
    int n, mx = 0; cin >> n;
    for (int i = 0; i < n; i ++) {
        string s; cin >> s;
        int a = s[0] - '0', b = s.back() - '0';
        dp[b] = max(dp[b], dp[a] + 1), mx = max(mx, dp[b]);
    }
    cout << n - mx << endl;
    return 0;
}

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

題意描述

小藍(lán)得到了一副大小為M × N 的格子地圖，可以將其視作一個(gè)只包含字符‘0’（代表海水）和‘1’（代表陸地）的二維數(shù)組，地圖之外可以視作全部是海水，每個(gè)島嶼由在上/下/左/右四個(gè)方向上相鄰的‘1’ 相連接而形成。

在島嶼A 所占據(jù)的格子中，如果可以從中選出k 個(gè)不同的格子，使得他們的坐標(biāo)能夠組成一個(gè)這樣的排列：($x_0,y_0$),($x_1,y_1$)… ($x_{k?1},y_{k?1}$)，其中($x_{(i+1)}\%k,y_{(i+1)}\%k$) 是由($x_i,y_i$) 通過上/下/左/右移動(dòng)一次得來的(0 ≤ i ≤ k ? 1)，此時(shí)這k 個(gè)格子就構(gòu)成了一個(gè)“環(huán)”。如果另一個(gè)島嶼B 所占據(jù)的格子全部位于這個(gè)“環(huán)” 內(nèi)部，此時(shí)我們將島嶼B 視作是島嶼A 的子島嶼。若B 是A 的子島嶼，C 又是B 的子島嶼，那C 也是A 的子島嶼。

請(qǐng)問這個(gè)地圖上共有多少個(gè)島嶼？在進(jìn)行統(tǒng)計(jì)時(shí)不需要統(tǒng)計(jì)子島嶼的數(shù)目。

dfs | 連通塊

本題有兩種類型的頂點(diǎn), 一種是’海水’, 如果A海頂點(diǎn)在B海頂點(diǎn)的周圍8個(gè)格子內(nèi), 那兩個(gè)海頂點(diǎn)就算連通的.

另一個(gè)是’陸地’, 只有A在B的上下左右四個(gè)方格內(nèi), 兩個(gè)陸地才是連通的.

地圖外的方格我們?nèi)恳暈楹＃?與地圖外的海連通的海都視為外海， 可以發(fā)現(xiàn)， 接觸到了外海的島嶼， 就一定不是其它島嶼的子島。

所以在地圖周圍一圈， 我們?cè)黾右蝗?作為外海， dfs遍歷外海每一個(gè)方格， 若與外海方格相鄰的島嶼未被遍歷過，那么這就是一個(gè)新的島嶼， 再用一個(gè)dfs去遍歷這個(gè)島。

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int g[N][N], n, m, res = 0;
bool st[N][N];
int dx[] = {0, 0, 1, -1},
    dy[] = {1, -1, 0, 0};

void dfs_1(int r, int c) {
    st[r][c] = true;
  	//四向連通
    for (int i = 0; i < 4; i ++) {
        int x = dx[i] + r, y = dy[i] + c;
        if (st[x][y] || g[x][y] == 0) continue;
        dfs_1(x, y);
    }
}

void dfs_0(int r, int c) {
    st[r][c] = true;
    //八向連通
    for (int i = -1; i <= 1; i ++)
        for (int j = -1; j <= 1; j ++) {
            int x = r + i, y = c + j;
            if (x < 0 || x > n + 1 || y < 0 || y > m + 1 || st[x][y]) continue;
            if (g[x][y] == 0) dfs_0(x, y);
            else dfs_1(x, y), res ++;
        }
}

int main () {
    int T; cin >> T;
    while (T --) {
        memset(g, 0, sizeof g);
        memset(st, false, sizeof st);
        cin >> n >> m; res = 0;
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++) {
                char c; cin >> c;
                g[i][j] = c - '0';
            }
        dfs_0(0, 0);//從一個(gè)外海方格開始dfs
        cout << res << endl;
    }
    return 0;
}

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

題意描述

程序猿圈子里正在流行一種很新的簡(jiǎn)寫方法：對(duì)于一個(gè)字符串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長(zhǎng)度代替。例如internationalization簡(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è)字符$c_1$ 和$c_2$，請(qǐng)你計(jì)算S 有多少個(gè)以$c_1$ 開頭$c_2$ 結(jié)尾的子串可以采用這種簡(jiǎn)寫？

前綴和

設(shè)p[i]為前i個(gè)字符中$c_1$字符的個(gè)數(shù), 則對(duì)于下標(biāo)為j的$c_2$字符, 以其結(jié)尾且可以簡(jiǎn)寫的子串?dāng)?shù)量即為p[j - k + 1]

參考代碼

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll p[N], res;

int main () {
    int k; cin >> k;
    string s; char a, b; cin >> s >> a >> b;
    for (int i = 1; i <= s.size(); i ++) p[i] = p[i - 1] + (s[i - 1] == a);
    for (int i = k; i <= s.size(); i ++)
        if (s[i - 1] == b) res += p[i - k + 1];
    cout << res << endl;
    return 0;
}

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

題意描述

給定一個(gè)長(zhǎng)度為N 的整數(shù)數(shù)列：$A_1,A_2...A_N$。

你要重復(fù)以下操作K 次：每次選擇數(shù)列中最小的整數(shù)（如果最小值不止一個(gè)，選擇最靠前的），將其刪除。并把與它相鄰的整數(shù)加上被刪除的數(shù)值。

輸出K 次操作后的序列。

雙向鏈表 | 最小堆

由于要進(jìn)行大量的刪除操作, 不難想到可以使用鏈表.

而本題需要?jiǎng)討B(tài)的求最小值, 顯然可以使用堆.

每次從堆中取出最小值的下標(biāo), 然后在鏈表中刪除它.

但本題特殊點(diǎn)在于將其刪除。并把與它相鄰的整數(shù)加上被刪除的數(shù)值, 所以會(huì)導(dǎo)致還在堆中的元素的權(quán)的變化.

我們可以注意到, 每次刪除操作只會(huì)讓一些元素變大, 而不會(huì)讓元素變小. 也就是, 可能會(huì)讓原本的最小值變成不是最小值.

因此我們?nèi)〕龆阎械淖钚≈禃r(shí), 需要將此元素的排序權(quán)和實(shí)際的值進(jìn)行對(duì)比, 如果實(shí)際的值變大了, 則當(dāng)前元素并不一定是最小值, 需要重新放回堆中.

參考代碼

每次刪除操作最多會(huì)讓兩個(gè)元素的值變化, 因此從堆中取出的次數(shù)是k的線性, 時(shí)間復(fù)雜度為$O(n+k)\log n$

//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll v[N], l[N], r[N];

void del(int x) {
    r[l[x]] = r[x], l[r[x]] = l[x];
    v[l[x]] += v[x], v[r[x]] += v[x];
}

int main () {
    int n, k; cin >> n >> k;
    r[0] = 1, l[n + 1] = n;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;
    for (int i = 1; i <= n; i ++)
        cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});
    while (k --) {
        auto p = h.top(); h.pop();
        if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;
        else del(p.second);
    }
    int head = r[0];
    while (head != n + 1) {
        cout << v[head]<< " ";
        head = r[head];
    }
    return 0;
}

試題I: 景區(qū)導(dǎo)游

題意描述

某景區(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)：A1; A2; : : : ; AK。今天由于時(shí)間原因，小明決定跳過其中一個(gè)景點(diǎn)，只帶游客按順序游覽其中K ? 1 個(gè)景點(diǎn)。具體來說，如果小明選擇跳過Ai，那么他會(huì)按順序帶游客游覽 (1 ≤ i ≤ K)。請(qǐng)你對(duì)任意一個(gè)Ai，計(jì)算如果跳過這個(gè)景點(diǎn)，小明需要花費(fèi)多少時(shí)間在景點(diǎn)之間的擺渡車上？

帶權(quán)LCA

要確定的一點(diǎn)是， 由于題中的圖是一棵樹， 所以對(duì)于任意兩個(gè)頂點(diǎn)， 它們的最短路徑就是它們的簡(jiǎn)單路徑。

求樹中兩個(gè)結(jié)點(diǎn)的最短路徑， 可以想到LCA。

設(shè)$dist[u]$為u頂點(diǎn)到根結(jié)點(diǎn)的距離， 那么u和v的距離即為$dist[u]+dist[v]?2?dist[lca(u,v)]$.

因此本題就是一道LCA的模板題， 使用倍增或者tarjan都是可以的, 具體的算法知識(shí)請(qǐng)自行去學(xué)習(xí)。

距離可能會(huì)爆int， 因此建議是所有整型都用long long， 避免麻煩。

參考代碼

//
// Created by trudbot on 2023/4/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
vector<pair<int, int>> g[N];
ll dep[N], f[N][30], dist[N];

void dfs(int u, int fa, ll d) {
    dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (auto &p : g[u]) {
        if (p.first == fa) continue;
        dfs(p.first, u, d + p.second);
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 20; i >= 0; i --) {
        if (dep[f[a][i]] >= dep[b]) a = f[a][i];
        if (a == b) return a;
    }
    for (int i = 20; i >= 0; i --) {
        if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    }
    return f[a][0];
}

ll get(int a, int b) {
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int main () {
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; i ++) {
        int u, v, t; cin >> u >> v >> t;
        g[u].push_back({v, t}), g[v].push_back({u, t});
    }
    vector<int> a(k);
    for (auto &x : a) cin >> x;
    dfs(1, 0, 0);
    ll sum = 0;
    for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]);
    for (int i = 0; i < k; i ++) {
        ll ans = sum;
        if (i != 0) ans -= get(a[i], a[i - 1]);
        if (i != k - 1) ans -= get(a[i], a[i + 1]);
        if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]);
        cout << ans << " ";
    }
    return 0;
}

試題J: 砍樹

題意描述

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

樹上差分

同上題我們知道， 樹中兩個(gè)結(jié)點(diǎn)的簡(jiǎn)單路徑是唯一的。

因此如果我們能找到一條邊， 每組數(shù)對(duì)的兩個(gè)結(jié)點(diǎn)的簡(jiǎn)單路徑都要經(jīng)過這條邊， 那么就可以滿足題意。

這時(shí)我們可以很簡(jiǎn)單的想到思路， 對(duì)于數(shù)對(duì)$(a,b)$， 我們遍歷a到b路徑上的每一條邊， 讓其權(quán)值加一。

最后若存在權(quán)值為m的邊， 那么就滿足題意。

但這樣做時(shí)間復(fù)雜度顯然最壞是$O(nm)$， 不達(dá)標(biāo)。

這時(shí)候我們可以用到樹上差分優(yōu)化這一過程， 同理這里不會(huì)贅述它是什么， 請(qǐng)自行去學(xué)習(xí)相關(guān)知識(shí)。文章來源地址http://www.zghlxwxcb.cn/news/detail-439738.html

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<pair<int, int>> g[N];
int dep[N], f[N][20], cnt[N], w[N];

void init(int u, int fa) {
  dep[u] = dep[fa] + 1, f[u][0] = fa;
  for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
  for (auto &e : g[u]) {
    if (e.first != fa) init(e.first, u), w[e.first] = e.second;
  }
}

int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int i = M; i >= 0; i --) {
    if (dep[f[a][i]] >= dep[b]) a = f[a][i];
    if (a == b) return a;
  }
  for (int i = M; i >= 0; i --) {
    if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
  }
  return f[a][0];
}

void add(int a, int b) {
  int LCA = lca(a, b);
  cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2;
}

void dfs(int u, int fa) {
  for (auto &e : g[u]) {
    if (e.first != fa) 
      dfs(e.first, u), cnt[u] += cnt[e.first];
  }
}

int main () {
  int n, m; cin >> n >> m;
  for (int i = 1; i < n; i ++) {
    int a, b; cin >> a >> b;
    g[a].push_back({b, i}), g[b].push_back({a, i});
  }
  init(1, 0);
  for (int i = 0; i < m; i ++) {
    int a, b; cin >> a >> b;
    add(a, b);
  }
  dfs(1, 0);
  int res = -1;
  for (int i = 1; i <= n; i ++) 
    if (cnt[i] == m && (w[i] > res)) res = w[i];
  cout << res << endl;
  return 0;
}

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