什么叫暴力，怎么打暴力，怎么骗分，为什么连暴力思路都没有，这或许是很多刚接触蓝桥杯的人有的疑问，我当时也是这样，不明白为什么大家都说这玩意打打暴力可以随便拿省一，现在距离蓝桥杯已经过去四个月了，现在回看这些题目感觉都比较容易了，为此写一篇比较完整的总结，题解中会含部分暴力代码，供刚刚接触蓝桥杯的新生参考

可以总结一下，如果你纯打暴力，一二题大概有25分，在四川已经省二前列了，后面第五题大概暴力又有9分，第六题打打暴力，估计拿1-2分，听省一同学说省一应该稳了，个人非常不建议干输出样例这种事情，因为没啥用，样例一般不在测试点里，打暴力是合理骗分，我想的只是没那么多没那么巧妙而已，输出样例就太low了，顺带一提，这次的填空有点ex，如果不会填空没必要心态炸裂

还有一些血的教训，如果作为毫无基础的大一新生，刷不完基础课，提高课，蓝桥杯辅导课，都没什么关系，不要过度依赖课程，重要的是要自己上手解决一些问题，对问题的解法大概有个头绪，对自己写的算法的复杂度心中有数，对特定数据范围该用什么复杂度的算法心中有数(这个可以参考y总发的根据数据范围反推算法)。蓝桥杯辅导课可能对刚刷完基础课的同学会比较困难，但做里面的题的时候也应该自己想想大概怎么做，可能最后结果是tle，wa，都没什么关系，如果盲目的听题解出现的结果就是我会做这一道题了，但也只会这一道题，我当时准备的时候看到那些题感觉也想不出正解，就直接刷视频，蓝桥杯之前我刷完了基础课，在蓝桥杯辅导课的排名是180名，相对来说也算刷了不少题了，最后还是啥都不会，比赛时打了一个暴力草草收尾，归根结底就是技巧学的多，可是基础算法并不扎实

第一题
小蓝有一个神奇的炉子用于将普通金属O，冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性V，V是一个正整数，这意味着消耗 V个普通金属O，恰好可以冶炼出一个特殊金属 X，当普通金属O的数目不足V时，无法继续冶炼。
现在给出了N条冶炼记录，每条记录中包含两个整数A和B，这表示本次投入了A个普通金属 O，最终冶炼出了B个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属O不会累加到下一次的冶炼当中。根据这N条冶炼记录，请你推测出转换率V的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式
第一行一个整数 N，表示冶炼记录的数目。
接下来输入N行，每行两个整数 A、B，含义如题目所述。

输出格式
输出两个整数，分别表示V可能的最小值和最大值，中间用空格分开。

数据范围
对于30%的评测用例，1 ≤ N ≤ 10^2。
对于60%的评测用例，1 ≤ N ≤ 10^3。
对于100%的评测用例，1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^9。

对于这题来说，我们可以假设一个maxv,一个minv，对ai而言，ai / minv = ai / maxv，那么如何求得maxv，其实很简单，遍历所有ai / bi，取最小的那个即可，接下来的难点是如何求minv，我们首先可以赌，maxv和minv的差距不大，我们从maxv开始减，直到减到ai / minv != ai / maxv为止，这就是所谓的暴力，那么我们先看暴力的代码

#include <iostream>
#define int long long

using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];

signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i] >> b[i];
    int maxv = 2e9;
    for (int i = 0; i < n; i ++)
    {
        maxv = min(maxv, a[i] / b[i]);
    }
    int minv;
    for (int i = maxv; i > 0; i --)
    {
        bool success = true;
        for (int j = 0; j < n; j ++)
        {
            if (a[j] / i != b[j])
            {
                success = false;
                break;
            }
        }
        if (!success) break;
        minv = i;
    }
    cout << minv << ' ' << maxv << endl;
    return 0;
}

经过测试，该代码可以过7个点，已经可以拿省三了，乐
当然不能AC的肯定还不够完美，我们可以列出式子，b * v <= a, (b + 1) * v > a，得到最小值为a / (b + 1) + 1, 最大值为a / b
AC code

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

signed main()
{
    int n;
    cin >> n;
    int minx = 0, maxx = 1e9;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        minx = max(a / (b + 1) + 1, minx);
        maxx = min(a / b, maxx);
    }
    cout << minx << ' ' << maxx << '\n';

    return 0;
}

第二题
有N架飞机准备降落到某个只有一条跑道的机场。其中第i架飞机在 Ti时刻到达机场上空，到达时它的剩余油料还可以继续盘旋Di个单位时间，即它最早可以于Ti时刻开始降落，最晚可以于Ti+Di时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断N架飞机是否可以全部安全降落。

输入格式
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。对于每组数据，第一行包含一个整数 N。
以下N行，每行包含三个整数：Ti，Di和Li。

输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

数据范围
对于30%的数据，N ≤ 2。
对于100%的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti, Di, Li ≤ 10^5。

思路：我认为一定要对数据范围敏感，对于100%的数据来说一共才有10个飞机，那么我们可以优先考虑全排列，这就是暴力，我把所有可能出现的降落方式都枚举一遍，如果都不行的话就是no，有一个可以就是yes，可能有些刚入坑的同学，会往排序贪心上想，比如我就是，但是你要想，排序是nlogn的，相当于就只计算50次左右，C++一秒计算1e8次，你就计算50次不是亏麻了吗
还有，注意30%的分是两架飞机，直接特判就行了，不要觉得拿不到满分就不写了

在不开O2的情况下全排列会TLE

#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 15;
struct plane
{
    int x, y, z;
}a[N];
int num[N];

int main()
{
    int T; cin >> T;
    while (T --)
    {
        int n; cin >> n;
        for (int i = 0; i < n; i ++) num[i] = i + 1;
        for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y >> a[i].z;
        bool suc = false;
        do
        {
            int lst = 0, flag = true;
            for (int i = 0; i < n; i ++)
            {
                int id = num[i];//映射回去
                if (lst > a[id].x + a[id].y)
                {
                    flag = false;
                    break;
                }
                lst = max(lst, a[id].x) + a[id].z;
            }
            if (flag) 
            {
                suc = true;
                break;
            }
        }while (next_permutation(num, num + n));
        if (suc) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

当然这种做法时间复杂度肯定不够优秀，其实我们会发现有一些情况根本不会发生，因此不用考虑，我们可以考虑采取搜索，剪枝的做法来降低时间复杂度(当然此题还有状态压缩解法，不过个人感觉没有必要弄的这么麻烦)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 15;
struct plane
{
    int x, y, z;
}a[N];
bool st[N];
int n;

bool dfs(int u, int last)
{
    if (u == n) return true;//当u == n表示我们已经搜索完n架飞机了
    for (int i = 1; i <= n; i ++)
    {
        if (!st[i] && (last <= a[i].y + a[i].x))//其实在这一行已经剪去不少情况了
        {
            st[i] = true;
            if (dfs(u + 1, max(a[i].x, last) + a[i].z)) return true;
            st[i] = false;
        }
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        cin >> n;
        memset(st, false, sizeof st);
        for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y >> a[i].z;
        if (dfs(0, 0)) puts("YES");
        else puts("NO");
    }
    return 0;
}

第三题
对于一个长度为K的整数数列：A1,A2,…,AK，我们称之为接龙数列当且仅当Ai的首位数字恰好等于 Ai−1的末位数字 (2≤i≤K)。
例如 12,23,35,56,61,11是接龙数列；12,23,34,56不是接龙数列，因为56的首位数字不等于34的末位数字。所有长度为1的整数数列都是接龙数列。

现在给定一个长度为N的数列 A1,A2,…,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式
第一行包含一个整数N。
第二行包含N个整数 A1,A2,…,AN。

输出格式
一个整数代表答案。
数据范围对于20%的数据，1 ≤ N ≤ 20。
对于50%的数据，1 ≤ N ≤ 10000。
对于100%的数据，1 ≤ N ≤ 10 ^ 5，1 ≤ Ai ≤ 109。所有Ai保证不包含前导 0。

思路：很明显的dp，我并没有想到什么暴力写法，或许可以试试搜索？但估计只有前20%的点，只能说dp的划分如果没见过可能会比较吃亏，我们把首字母和末尾记录下来，中间的不重要，那么状态转移就非常简单了，当时写这个题很迷茫，后来学了图论之后才慢慢熟悉这种划分方式(可能是我太废物了呜呜呜)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;
int f[N];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int n; cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        string x; cin >> x;
        int l = x[0] - '0', r = x.back() - '0';
        f[r] = max(f[r], f[l] + 1);
        res = max(f[r], res);
    }
    cout << n - res << endl;
    return 0;
}

第四题
小蓝得到了一副大小为 M×N的格子地图，可以将其视作一个只包含字符0（代表海水）和1（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。在岛屿 A所占据的格子中，如果可以从中选出 k个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),…,(xk−1,yk−1)，其中 (x(i+1)%k,y(i+1)%k)是由 (xi,yi)通过上/下/左/右移动一次得来的 (0≤i≤k−1)，此时这k个格子就构成了一个 “环”。如果另一个岛屿 B所占据的格子全部位于这个 “环” 内部，此时我们将岛屿B视作是岛屿A的子岛屿。若B是A的子岛屿，C又是B的子岛屿，那C也是A的子岛屿。

请问这个地图上共有多少个岛屿？

在进行统计时不需要统计子岛屿的数目。

输入格式
第一行一个整数T，表示有T组测试数据。

接下来输入T组数据。

对于每组数据，第一行包含两个用空格分隔的整数 M、N表示地图大小；接下来输入M行，每行包含 N个字符，字符只可能是 0 或 1。

输出格式
对于每组数据，输出一行，包含一个整数表示答案。

数据范围对于 30% 的评测用例，1 ≤ M, N ≤ 10。
对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。

很明显的一道bfs。相信大家都能看出来，难点在如何判环，其实运用了一个小trick，就是一个不被包围的岛，是可以扩展到边界的，被包围的岛屿一定会被其他岛挡住，因此我们使用两个bfs即可，考场上如果不会写，可以赌测试样例里有没有被包围岛屿的测试样例，写一个bfs撞运气

#include <iostream>
#include <queue>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 60;
bool st[N][N];
int g[N][N];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int n, m;

bool bfs1(int a, int b)
{
    memset(st, 0, sizeof st);
    queue<PII> q;
    q.push({a, b});
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 8; i ++)
        {
            int k1 = t.x + dx[i], k2 = t.y + dy[i];
            if (k1 < 0 || k1 >= n || k2 < 0 || k2 >= m) return true;
            if (st[k1][k2] || g[k1][k2] == 1) continue;
            q.push({k1, k2});
            st[k1][k2] = true;
        }
    }
    return false;
}

void bfs(int a, int b)
{
    queue<PII> q;
    q.push({a, b});
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++)
        {
            int k1 = t.x + dx[i], k2 = t.y + dy[i];
            if (k1 < 0 || k1 >= n || k2 < 0 || k2 >= m) continue;
            if (st[k1][k2] || g[k1][k2] == 0) continue;
            q.push({k1, k2});
            st[k1][k2] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T --)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
            {
                char s; cin >> s;
                g[i][j] = s - '0';
            }
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
            {
                if (g[i][j] == 1 && !bfs1(i, j)) g[i][j] = 0; 
            }
        memset(st, 0, sizeof st);
        int cnt = 0;
        for (int i = 0; i < n; i ++)
        {
            for (int j = 0; j < m; j ++)
            {
                if (g[i][j] == 1 && !st[i][j])
                {
                    bfs(i, j);
                    cnt ++;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

第五题
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes 简写成 K8s，Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于K的字符串都可以采用这种简写方法（长度小于K的字符串不配使用这种简写）。给定一个字符串S和两个字符c1和c2，请你计算S有多少个以c1开头c2结尾的子串可以采用这种简写？

输入格式
第一行包含一个整数 K。
第二行包含一个字符串S和两个字符c1和c2。

输出格式
一个整数代表答案。

数据范围
对于 20% 的数据，2 ≤ K ≤ |S| ≤ 10000。
对于 100% 的数据，2≤K≤|S|≤5×10^5。S只包含小写字母。c1和 c2都是小写字母。
|S|代表字符串 S 的长度。

思路：首先想暴力怎么写，我们是不是可以枚举每个c1,然后对每个c1再从i + k - 1的地方开始枚举，就很容易写出来，时间复杂度n ^ 2,但能过6个点
TLE写法

#include <iostream>
#include <cstring>
#define int long long

using namespace std;

signed main()
{
    string s;
    char s1, s2;
    int n; cin >> n;
    cin >> s >> s1 >> s2;
    int lst = 0, ans = 0, cnt = 0;
    for (int i = 0; i < s.size(); i ++)
    {
        if (s[i] == s1) 
        {
            for (int j = i + n - 1; j < s.size(); j ++)
            {
                if (s[j] == s2) ans ++;
            }
        }
    }
    cout << ans << endl;
}

再想正解怎么写，我们可以把c1，c2的下标分别存到两个vector里，然后枚举c1的坐标再二分求有多少个大于等于i + n - 1的数，直接lowerbound即可，复杂度nlogn
AC code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;


signed main()
{
    string s;
    char s1, s2;
    int n; cin >> n;
    cin >> s >> s1 >> s2;
    vector<int> v1, v2;
    for (int i = 0; i < s.size(); i ++)
    {
        if (s[i] == s1) v1.push_back(i);
        if (s[i] == s2) v2.push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < v1.size(); i ++)
    {
        int k = v1[i];
        int x = lower_bound(v2.begin(), v2.end(), k + n - 1) - v2.begin();
        int cnt = v2.size() - x;
        ans += cnt;
    }
    cout << ans << endl;
}

第六题
给定一个长度为N的整数数列：A1,A2,…,AN。你要重复以下操作K次：每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除，并把与它相邻的整数加上被删除的数值。
输出K次操作后的序列。

输入格式
第一行包含两个整数N和K。

第二行包含N个整数，A1,A2,A3,…,AN。

输出格式
输出 N−K个整数，中间用一个空格隔开，代表K次操作后的序列。

数据范围
对于20%的数据，1 ≤ K < N ≤ 10000。
对于100%的数据，1 ≤ K < N ≤ 5 × 10^5，0 ≤ Ai ≤ 10^8。

思路：从这题开始后面打暴力收益就不大了，因为本题有两个点，k是躲不掉的，所以每次操作只能在logn的时间复杂度内进行，首先要想到priority_queue或者multiset，其次是双向链表维护左右两边的数，如果暴力去找左右节点的话时间复杂度为nklogn，20%的点都不好过，其次每次操作(我的方法而言)常数都比较大，所以这题就不贴暴力做法了(实话说我暴力是wa了，只能过一个点)
言归正传，这题想到堆排列，平衡树和双向链表就很简单了，首先双向链表维护左右两边的节点，然后每次删除最小节点并修改左右两边的节点即可，大概是5 * klogn，可能卡在边缘过

注意此题需要开O2，不然可能stl可能过不去，貌似蓝桥杯是开O2的，你也不想手写平衡树吧

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <set>
#define int long long

using namespace std;
typedef pair<int, int> PII;
const int N = 5e5 + 10;
int l[N], r[N], w[N], st[N], cnt[N];

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    int n, k; cin >> n >> k;
    r[0] = 1;
    for (int i = 1; i <= n; i ++) l[i] = i - 1, r[i] = i + 1;
    multiset<PII> s;
    for (int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        s.insert({w[i], i});
    }
    while (k --)
    {
        auto it = s.begin();
        int v = it -> first, id = it -> second;
        s.erase(it);
        int pre1 = w[l[id]], pre2 = w[r[id]], preid1 = l[id], preid2 = r[id];
        w[l[id]] += v, w[r[id]] += v;
        if (preid1 != 0) 
        {
            s.erase(s.find({pre1, preid1}));
            s.insert({w[l[id]], preid1});
        }
        if (preid2 != n + 1) 
        {
            s.erase(s.find({pre2, preid2}));
            s.insert({w[r[id]], preid2});   
        }
        l[r[id]] = l[id];
        r[l[id]] = r[id];
        st[id] = true;
    }
    for (int i = 1; i <= n; i ++) if (!st[i]) cout << w[i] << " ";
}

第七题
某景区一共有N个景点，编号 1 到 N。

景点之间共有 N−1条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K个景点：A1,A2,…,AK。

今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中K−1个景点。

具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1,A2,…,Ai−1,Ai+1,…,AK,(1≤i≤K)。

请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

输入格式
第一行包含2个整数 N 和 K。

以下 N−1 行，每行包含 3个整数 u, v 和 t，代表景点 u 和 v 之间有摆渡车线路，花费t个单位时间。

最后一行包含K个整数 A1,A2,…,AK 代表原定游览线路。

输出格式
输出 K 个整数，其中第 i 个代表跳过 Ai 之后，花费在摆渡车上的时间。

数据范围
对于20%的数据，2 ≤ K ≤ N ≤ 10^2。
对于40%的数据，2 ≤ K ≤ N ≤ 10^2。
对于100%的数据，2 ≤ K ≤ N ≤ 10^2，1 ≤ u, v, Ai ≤ N，1 ≤ t ≤ 10^5。保证 Ai 两两不同。

思路，一眼lca，由于比较板，属于没接触过不太可能自己想出来，所以直接写正解了，我们不难发现两点的距离是它们分别到它们lca的路径，那么思路就很简单了，直接先求出游览所有景区需要花费的时间，再分成两类讨论一下删除点后的时间，两类分别为删除起点或终点，和删除中间的点，对起点和终点而言，直接用tot - lca(起点，下一个点)或tot - lca(上一个点，终点)即可，对于中间的来说，需要减去它和左右两边的lca，再加上左右两边的lca即可

#include <iostream>
#include <vector>
#define int long long

using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
vector<PII> e[N];
int h[N], up[N][18], d[N][18], dist[N];
int w[N];

void dfs(int u, int fa)
{
    for (auto [v, w] : e[u])
    {
        if (v == fa) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        d[v][0] = w;
        for (int i = 1; i < 18; i ++)
        {
            up[v][i] = up[up[v][i - 1]][i - 1];
            d[v][i] = d[v][i - 1] + d[up[v][i - 1]][i - 1];
        }
        dfs(v, u);
    }
}

int lca(int a, int b)
{
    if (h[a] < h[b]) swap(a, b);
    int dist = 0;
    for (int i = 17; ~i; i --)
    {
        if (h[up[a][i]] >= h[b]) 
        {
            dist += d[a][i];
            a = up[a][i];
        }
    }
    if (a == b) return dist;
    for (int i = 17; ~i; i --)
    {
        if (up[a][i] != up[b][i])
        {
            dist += d[a][i] + d[b][i];
            a = up[a][i];
            b = up[b][i];
        }
    }
    dist += d[a][0] + d[b][0];
    return dist;
}


signed main()
{
    int n, k; cin >> n >> k;
    for (int i = 0; i < n - 1; i ++)
    {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (int i = 0; i < k; i ++) cin >> w[i];
    h[1] = 1;
    dfs(1, 0);
    int tot = 0;
    for (int i = 0; i < k - 1; i ++)
    {
        dist[i] = lca(w[i], w[i + 1]);
        tot += dist[i];
    }
    for (int i = 0; i < k; i ++)
    {
        int ans;
        if (i == 0) ans = tot - dist[i];
        else if (i == k - 1) ans = tot - dist[i - 1];
        else
        {
            ans = lca(w[i - 1], w[i + 1]);
            ans = ans + tot - dist[i - 1] - dist[i];
        }
        cout << ans << " ";
    }
}

注意，这题是可以树链剖分的，可以练习一下怎么把边权转化成点权
这里附上该题树链剖分的代码

#include <iostream>
#include <vector>
#define int long long

using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10;
vector<PII> e[N];
int son[N], nw[N], dfn[N], sz[N], fa[N];
int w[N], aim[N];
int up[N], h[N];
int dist[N];
int n, k;
int idx;
struct node
{
    int l, r, sum;
    void init(int _l, int _r, int _v)
    {
        l = _l, r = _r;
        sum = _v;
    }
}tr[4 * N];

void dfs1(int u, int father, int dep)
{
    h[u] = dep, sz[u] = 1, fa[u] = father;
    for (auto [v, wg] : e[u])
    {
        if (v == father) continue;
        dfs1(v, u, dep + 1);
        w[v] = wg;
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int t)
{
    dfn[u] = ++ idx, nw[idx] = w[u], up[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (auto [v, wg] : e[u])
    {
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

void pushup(int id)
{
    tr[id].sum = tr[id << 1].sum + tr[id << 1 | 1].sum;
}

void build(int id, int l, int r)
{
    if (l == r) 
    {
        tr[id].init(l, r, nw[l]);
        return;
    }
    int mid = l + r >> 1;
    tr[id].init(l, r, 0);
    build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

int query(int id, int ql, int qr)
{
    if (tr[id].l == ql && tr[id].r == qr) return tr[id].sum;
    int mid = tr[id].l + tr[id].r >> 1;
    if (qr <= mid) return query(id << 1, ql, qr);
    else if (ql > mid) return query(id << 1 | 1, ql, qr);
    else return query(id << 1, ql, mid) + query(id << 1 | 1, mid + 1, qr);
}

int query_path(int a, int b)
{
    int res = 0;
    while (up[a] != up[b])
    {
        if (h[up[a]] < h[up[b]]) swap(a, b);
        res += query(1, dfn[up[a]], dfn[a]);
        a = fa[up[a]];
    }
    if (h[a] < h[b]) swap(a, b);
    if (dfn[b] + 1 <= dfn[a]) res += query(1, dfn[b] + 1, dfn[a]);
    return res;
}

signed main()
{
    cin >> n >> k;
    for (int i = 0; i < n - 1; i ++)
    {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    for (int i = 0; i < k; i ++) cin >> aim[i];
    int tot = 0;
    for (int i = 0; i < k - 1; i ++)
    {
        dist[i] = query_path(aim[i], aim[i + 1]);
        tot += dist[i];
    }
    for (int i = 0; i < k; i ++)
    {
        int ans;
        if (i == 0) ans = tot - dist[i];
        else if (i == k - 1) ans = tot - dist[i - 1];
        else
        {
            ans = query_path(aim[i - 1], aim[i + 1]);
            ans = ans + tot - dist[i - 1] - dist[i];
        }
        cout << ans << " ";
    }
}

第八题
给定一棵由n个结点组成的树以及 m 个不重复的无序数对 (a1,b1),(a2,b2),…,(am,bm)，其中 ai互不相同，bi互不相同，ai≠bj(1≤i,j≤m)。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai,bi)满足 ai 和 bi不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 −1。

输入格式
输入共 n+m行，第一行为两个正整数 n,m。

后面 n−1 行，每行两个正整数 xi,yi表示第 i 条边的两个端点。

后面 m 行，每行两个正整数 ai,bi。

输出格式
一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

数据范围
对于 30% 的数据，保证 1 < n ≤ 1000。
对于 100% 的数据，保证 1 < n ≤ 10^5，1 ≤ m ≤ n/2。

看题解都说是lca加树上差分，我在这里再补一个树链剖分写法
本题我在补的时候并没有自己想出来，我是想的对a中所有点让它们的点权是1，b中所有点的点权是-1，对于每个切去的路径我们求一下他的子树之和(注意是求子节点的子树之和)如果发现点权和的绝对值是m，那么说明该边切了是正确的，但是注意，这种思路是错的。我目前不知道为什么，这个思路可以过6个点，但是后面有答案的测试样例貌似全是-1

补充：破案了，如果存在ai,bj(i != j)在一个子树中，就会找不到答案

正解思路：参考一个大佬的思路，将a, b的路径改为边权为1的路径，然后对每个边求一下边权，如果为m就说明该边是其中一个答案，属于树链剖分板子题

#include <iostream>
#include <vector>
#define int long long

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

struct node
{
    int l, r;
    int sum, add;
    void init(int _l, int _r, int _v)
    {
        l = _l, r = _r;
        sum = _v;
        add = 0;
    }
}tr[N * 4];
vector<int> e[N];
PII tot[N];
int dfn[N], nw[N], son[N], sz[N];
int fa[N], h[N], up[N], w[N];
int idx, n, m;

void dfs1(int u, int father, int dep)
{
    fa[u] = father, sz[u] = 1, h[u] = dep;
    for (auto v : e[u])
    {
        if (v == father) continue;
        dfs1(v, u, dep + 1);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int t)
{
    dfn[u] = ++ idx, nw[idx] = w[u], up[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (auto v : e[u])
    {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
void pushup(int id)
{
    tr[id].sum = tr[id << 1].sum + tr[id << 1 | 1].sum;
}

void setlazy(int id, int v)
{
    tr[id].sum += (tr[id].r - tr[id].l + 1) * v;
    tr[id].add += v;
}

void pushdown(int id)
{
    if (tr[id].add)
    {
        setlazy(id << 1, tr[id].add);
        setlazy(id << 1 | 1, tr[id].add);
        tr[id].add = 0;
    }
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        tr[id].init(l, r, 0);
        return;
    }
    int mid = l + r >> 1;
    tr[id] = {l, r};
    build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

void modify(int id, int ql, int qr, int v)
{
    if (tr[id].l == ql && tr[id].r == qr) 
    {
        setlazy(id, v);
        return;
    }
    int mid = tr[id].l + tr[id].r >> 1;
    pushdown(id);
    if (qr <= mid) modify(id << 1, ql, qr, v);
    else if (ql > mid) modify(id << 1 | 1, ql, qr, v);
    else modify(id << 1, ql, mid, v), modify(id << 1 | 1, mid + 1, qr, v);
    pushup(id);
}
int query(int id, int ql, int qr)
{
    if (tr[id].l == ql && tr[id].r == qr) return tr[id].sum;
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (qr <= mid) return query(id << 1, ql, qr);
    else if (ql > mid) return query(id << 1 | 1, ql, qr);
    return query(id << 1, ql, mid) + query(id << 1 | 1, mid + 1, qr);
}

void modify_path(int u, int v, int k)
{
    while (up[u] != up[v])
    {
        if (h[up[u]] < h[up[v]]) swap(u, v);
        modify(1, dfn[up[u]], dfn[u], k);
        u = fa[up[u]];
    }
    if (h[u] < h[v]) swap(u, v);
    if (dfn[v] + 1 <= dfn[u]) modify(1, dfn[v] + 1, dfn[u], k);
}

int query_path(int u, int v)
{
    int res = 0;
    while (up[u] != up[v])
    {
        if (h[up[u]] < h[up[v]]) swap(u, v);
        res += query(1, dfn[up[u]], dfn[u]);
        u = fa[up[u]];
    }
    if (h[u] < h[v]) swap(u, v);
    if (dfn[v] + 1 <= dfn[u]) res += query(1, dfn[v] + 1, dfn[u]);
    return res;
}
signed main()
{
    cin >> n >> m;
    for (int i = 0; i < n - 1; i ++)
    {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        tot[i] = {u, v};
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    for (int i = 0; i < m; i ++)
    {
        int a, b; cin >> a >> b;
        modify_path(a, b, 1);
    }
    int ans = -1;
    for (int i = 0; i < n - 1; i ++)
    {
        int u = tot[i].first, v = tot[i].second;
        if (query_path(u, v) == m) ans = i + 1;
    }
    cout << ans << endl;
}

最后有些话想对自己说，蓝桥杯一定不要怕麻烦，树上差分想不到就用树链剖分，启发式合并想不到就跑莫队，还想不到就暴力跑，双向搜索加哈希想不到就双向搜索加ump，双向搜索都想不到就单向搜索，还想不到就特判特殊情况，不要觉得这题好像拿不满了就不写了，一定要挣扎一下，哪怕wa了，也应该能有1-2分，蓝桥杯近年来题目不简单，但是获奖的分数不高，希望明年4月能拿到满意的排名