🎉🎉?目前持续总结更新，请持续关注！！！?🎉🎉
💗 大家好🤗🤗🤗，我是左手の明天！💗
📆 最近更新：2022 年 4 月 20 日，左手の明天的第?231?篇原创博客
🥇?更新于专栏：蓝桥杯预备营
目录
👍👍👍👍👍👍
🌟🌟?预祝各位在每一届中能够得到好的名次?🌟🌟
🚩跑步训练
??问题描述
?明要做?个跑步训练。 初始时，?明充满体?，体?值计为 10000。如果?明跑步，每分钟损耗600的体?。如果?明休息，每分钟增加 300 的体?。体?的损耗和增加都是均匀变化的。
?明打算跑?分钟、休息?分钟、再跑?分钟、再休息?分钟……如此循环。如果某个时刻?明的体?到达0，他就停?锻炼。 请问?明在多久后停?锻炼。
??思路分析
第1分钟消耗600体力，第2分钟提升300体力，那就每2分钟消耗300体力；只要最后剩下大于600就能完成这样的循环。
分情况讨论，当剩余体力大于600时，每2分钟消耗300体力；体力小于600时，直接计算。
因此可以使用递归算法
??代码
#include <iostream>
using namespace std;
int slove(int n)
{
int m = 0;
while(true)
{
// 体力大于600，还能进行下次循环
if(n > 600)
{
n -= 600; // 跑1分钟消耗600体力
}
else
{
return m + n / (600 / 60);
}
n += 300; // 休息1分钟提升300体力
m = m + 2 * 60; // 一个循环2分钟
}
}
// 递归算法
int slove_d(int n)
{
//体力不大于600，结束递归
if(n <= 600)
{
return n / (600 / 60);
}
// 每次循环2分钟， 消耗300体力
return 60 * 2 + slove_d(n - 300);
}
int main()
{
cout << slove(10000) << endl;
cout << slove_d(10000) << endl;
return 0;
}??结果
答案：3880
🚩跑步锻炼
??问题描述
小蓝每天都锻炼身体。正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
??思路分析
首先写一个判断日期是否合法的函数check，这个函数用来检查一个八位的日期是否合法。
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date)
{
int year = date / 10000; //年
int month = date % 10000 / 100; //月
int day = date % 100; //日
if(!month || month > 12 || !day ) return false;//如果月份大于12或者为零或者天数为零则该日期不合法
if(month != 2 && day > months[month]) return false;//在不是二月的情况下，该月实际天数大于该月最大天数，则该日期不合法
if(month == 2) //特判二月
{
if((year % 4 == 0&& year % 100 != 0) || (year % 400 == 0))//特判闰年
{
if(day > 29) return false;
}
else if( day > 28) return false;
}
return true;
}假设终点日期离起始日期
sum天，起始日期是星期六，那么(sum + 6) % 7 == 1就可以判断出这天是不是星期一，而(sum + 6) % 7 == 0代表星期日。
??代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date)
{
int year = date / 10000;
int month = date % 10000 / 100;
int day = date % 100;
if(!month || month > 12 || !day ) return false;//
if(month != 2 && day > months[month]) return false;
if(month == 2)
{
if((year % 4 == 0&& year % 100 != 0) || (year % 400 == 0))
{
if(day > 29) return false;
}
else if( day > 28) return false;
}
return true;
}
int main()
{
int res = 0,sum = 0;//sum记录相隔天数，res记录答案
for(int i = 20000101; i <= 20201001; i++) // 1 2 3
{
if(check(i))
{
res ++ ;
int month = i % 10000 / 100;
int day = i % 100;
if( day == 1 || (sum + 6) % 7 == 1 ) res++; //周一或月初,加一千米
sum ++ ;
}
}
cout<<res<<endl;
return 0;
}??结果
答案： 8879
🚩合并检测
??问题描述
新冠疫情由新冠病毒引起，最近在A国蔓延，为了尽快控制疫情，A国准备给?量民众进病毒核酸检测。然?，?于检测的试剂盒紧缺。
为了解决这?困难，科学家想了?个办法：合并检测。即将从多个?（k个）采集的标本放到同?个试剂盒中进?检测。如果结果为阴性，则说明这k个?都是阴性，??个试剂盒完成了 k 个?的检测。如果结果为阳性，则说明 ?少有?个?为阳性，需要将这 k 个?的样本全部重新独?检测（从理论上看， 如果检测前 k?1 个?都是阴性可以推断出第 k 个?是阳性，但是在实际操作中 不会利?此推断，?是将 k 个?独?检测），加上最开始的合并检测，?共使? 了 k + 1 个试剂盒完成了 k 个?的检测。 A 国估计被测的民众的感染率?概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？
??代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int N = 1000;
int ans;
int minn = 9999999;
int sum = 0;//试剂盒的数量
for (int k = 1;k <= 1000;k++) {
if (N % k == 0) {
sum = N / k + 10 * k;
}
else {
sum = N / k + 10 * k + 1;
}
if (sum < minn) {
minn = sum;
ans = k;
}
}
cout << ans;
return 0;
}??结果
答案：10
🚩分配口罩
??问题描述
某市市长获得了若?批?罩，给定每批?罩的数量，市长要把?罩分配给市内的2所医院。每一批口罩的数目如下：
9090400 8499400 5926800 8547000 4958200 4422600 5751200
4175600 6309600 5865200 6604400 4635000 10663400 8087200 4554000
由于物流限制，每?批?罩只能全部分配给其中?家医院。市长希望2所医院获得的?罩总数之差越?越好。 请你计算这个差最?是多少？
??代码
//dfs
#include<bits/stdc++.h>
using namespace std;
int ans = 9999;
int num[] = {9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200,
4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000};
void dfs(int n,int s1,int s2){
if(n==15){
ans = min(ans,abs(s1-s2));
return ;
}
dfs(n+1,s1+num[n],s2);//分配给第一家医院
dfs(n+1,s1,s2+num[n]);//分配给第二家医院
}
int main(){
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}??结果
答案：2400
🚩矩阵
??问题描述
把 1 ～ 2020 放在 2 × 1010 的矩阵里。
要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。
??思路分析
这题是个动态规划题， DP[i][j]表示第一层有i个数，第二层有j个数有多少种方案
题目要求同一行中右边比左边大， 同一列中下边比上边的大，所以 j <= i
- 当j < i时， DP[i][j]可以用此时少一个数的方案来表示，少一个数可以是DP[i - 1][j]，也可以是DP[i][j - 1]，DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
- 当j = i时， 因为要求，所以DP[i][j] = DP[i][j - 1]
??代码
#include <stdio.h>
int DP[1011][1011];
int main()
{
int i, j;
DP[1][0] = 1;
for (i = 1; i <= 1010; i++) DP[i][0] = 1;//初始化
for (i = 1; i <= 1010; i++) {
for (j = 1; j <= i; j++) {
if (i == j) DP[i][j] = DP[i][j - 1];
else DP[i][j] = (DP[i - 1][j] + DP[i][j - 1]) % 2020;
}
}
printf("%d", DP[1010][1010]);
return 0;
} ??结果
答案：1340
🚩完美平方数
??问题描述
如果整个整数X本?是完全平?数，同时它的每?位数字也都是完全平?数，我们就称X是完美平?数。 前?个完美平?数是 0、1、4、9、49、100、144…
请你计算第 2020 个完美平?数是多少？
??代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
bool hs[11] = { false };
int main() {
int cnt = 0;
hs[0] = 1, hs[1] = 1,hs[4] = 1, hs[9] = 1;
for (int i = 0;i <= 100000000;i++) {
int temp = i * i;
int flag = 1;
string str = to_string(temp);
for (int j = 0;j < str.length();j++) {
if (!hs[str[j] - '0']) {
flag = 0;break;
}
}
if (flag) {
cnt++;
cout << cnt<<endl;
}
if (cnt == 2020) {
cout << temp << endl;
return 0;
}
}
}//i=13786156 ans=1499441040??结果
答案：1499441040
🚩解码
??问题描述
?明有?串很长的英?字母，可能包含?写和?写。在这串字母中，有很多连续的是重复的。?明想了?个办法将这串字母表达得更短：将连续的?个相同字母写成字母 + 出现次数的形式。
例如，连续的5个a，即aaaaa，?明可以简写成a5（也可能简写成 a4a、 aa3a 等）。
对于这个例?：HHHellllloo，?明可以简写成 H3el5o2。为了?便表达，?明不会将连续的超过9个相同的字符写成简写的形式。
现在给出简写后的字符串，请帮助?明还原成原来的串。
输入
输入一行包含一个字符串。
输出
输出一个字符串，表示还原后的串。
样例输入
H3el5o2样例输出
HHHellllloo
??代码
#include<bits/stdc++.h>
using namespace std;
//将字符串从下标begin开始，全部向后退一位，并且str[begin]改为字符a
void push_1(char str[], int begin, char a) {
int i, j;
for (i = strlen(str); i > begin; i--) {
str[i] = str[i - 1];
}
str[begin] = a;
}
//将字符串从下标begin+1开始，全部向前进一位，并且字符串最后一位 置为空（'\0'）
void back_1(char str[], int begin) {
int i, j;
int length = strlen(str) - 1;
for (i = begin; i < strlen(str) - 1; i++) {
str[i] = str[i + 1];
}
str[length] = '\0';
}
int main() {
char str[1000000] = {};
cin >> str;
int i, j, temp;
int number = 0;
for (i = 0; i < strlen(str); i++) {
if (str[i] >= '1' && str[i] <= '9') {
number = (int)str[i] - 48; //计算出数字
if (number == 1) { //当为1时，不动，后面向前进一位，排掉此处的"1"
back_1(str, i);
}
else { //当数字不为1时
for (j = 1; j < number; j++) {
if (j == 1) { //第一个数直接将数字换成字符str[i-1]
str[i] = str[i - 1];
}
else //否则字符串往后退，并且添加重复字符str[i-1]
push_1(str, i, str[i - 1]);
}
}
}
}
cout << str;
return 0;
}
🚩走方格
??问题描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第??行，从左到右依次为第 1 至第??列，每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。
只能向右或者向下走。
注意，如果行号和列数都是偶数，不能走入这一格中。
问有多少种方案。
输入
输入一行包含两个整数 n，m?。
输出
输出一个整数，表示答案。
样例输入
3 4样例输出
2
??方法一：dfs解法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,ans;
void dfs(int x,int y)
{
if(x > n || y > m) return;
if(x%2 == 0 && y%2 == 0) return;
if(x == n && y == m) ans++;
dfs(x + 1,y);
dfs(x,y+1);
return;
}
int main()
{
cin>>n>>m;
if(n%2 == 0 && m%2 == 0) ans = 0;
else dfs(1,1);
cout<<ans<<endl;
return 0;
}
??方法二：dp解法
状态表示：f[i][j] 表示走到i，j时的走法数量。
判断，如果i与j没有同时为偶数，下一个状态就等于上一个状态往右的走法+往下的走法，这里不用重新判断上一个状态的ij是否同时为偶数，因为f[i][j]初始化就是0，不符合就不加。
状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,ans;
int f[35][35];
int main()
{
cin>>n>>m;
if(n%2 == 0 && m%2 == 0) cout<<"0";
else
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1) f[i][j] = 1;//初始化一下，第一格走法为1
else if(i % 2 == 1 || j % 2 == 1) f[i][j] = f[i - 1][j] + f[i][j - 1];
}
cout<<f[n][m]<<endl;
}
return 0;
}
🚩整数小拼接
??问题描述
给定?个长度为n的数组A1,A2,···,An。你可以从中选出两个数Ai和Aj(i不等于j)，然后将Ai和Aj?前?后拼成?个新的整数。
例如12和345可以拼成12345或34512。注意交换Ai和Aj的顺序总是被视为2种拼法，即便是Ai=Aj时。请你计算有多少种拼法满?拼出的整数?于等于 K。
输入格式
第一行包含 2 个整数 n 和 K。第二行包含 n 个整数 A1,A2,???,An。
输出格式
一个整数代表答案。输入样例：
4 33
1 2 3 4输出样例：
8
??方法：哈希+二分
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
typedef unsigned long long ull;
ull hash_table[11][N];
ll a[N],k;
int n;
ll cal(ull q[],int idx,ll target)
{
if(q[0] > target) return 0;
int l = 0,r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= target)
l = mid;
else
r = mid - 1;
}
return l >= idx ? l : l + 1;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a,a + n);
for (int i = 0; i < n; i ++ )
{
ll t = a[i];
for (int j = 0; j < 11; j ++ )
{
hash_table[j][i] = t;
t = t * 10;
}
}
ll res = 0;
for (int i = 0; i < n; i ++ )
{
int len = to_string(a[i]).size();
res += cal(hash_table[len],i,k - a[i]);
}
cout<<res<<endl;
return 0;
}
?🚩超级胶水
??问题描述
?明有n颗??，按顺序摆成?排。他准备?胶?将这些??粘在?起。每颗??有??的重量，如果将两颗??粘在?起，将合并成?颗新的??，重量是这两颗??的重量之和。
为了保证??粘贴牢固，粘贴两颗??所需要的胶?与两颗??的重量乘积成正?，本题不考虑物理单位，认为所需要的胶?在数值上等于两颗??重量的乘积。
每次合并，?明只能合并位置相邻的两颗??，并将合并出的新??放在原来的位置。
现在，?明想?最少的胶?将所有??粘在?起，请帮助?明计算最少需要多少胶?。
输入样例1：
3 3 4 5输出样例1：
47输入样例2：
8 1 5 2 6 3 7 4 8输出样例2：
546
??数学归纳法
数学归纳法证明：
设总花费为f
当n=2时，设石头重量分别为a,b，则f=a*b正确;
当n=3时，设石头重量分别为a,b,c，
则所有合并方式分别为:
f1=a*b+(a+b)*c=a*b+a*c+b*c;
f2=a*c+(a+c)*b=a*b+a*c+b*c;
f3=b*c+(b+c)*a=a*b+a*c+b*c;
f=f1=f2=f3，正确;
假设当n=k时结论正确,设石头重量分别为a1,a2,...ak
即f=a1*a2+a1*a3+...+a1*an+...+a(k-1)*ak
当n=k+1时，设石头重量分别为a1,a2,...ak,a(k+1)
无论将a(k+1)在哪一步进行合并，
其都可以看成是a(k+1)与ai的一个置换(1<=i<=k)
设a(k+1)与其中的ai进行了置换，
石头表示为(a1,a2,...,a(k+1),...ak),ai
对于前面括号中的部分，由假设的n=k的情况可以得到:
f1=a1*a2+...a1*an+...a(k+1)*a(i+1)+...+a(k+1)*ak+...+a(k-1)*ak
对前面括号的合并后可以看成剩两堆石头X,ai，
其中X的重量为a1+a2+...+a(k+1)+...+ak
对数量为2的情况，
花费f2=(a1+a2+...+a(k+1)+...+ak)*ai
=a1*ai+a2*ai+...ak*ai+a(k+1)*ai
故当n=k+1时，
总花费为f=f1+f2=a1*a2+...+a1*a(k+1)+...+ak*a(k+1)
因此假设正确。??代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+6;
typedef long long ll;
ll num[maxn];
ll sum,ans;
int main()
{
int i,j;
int n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
}
sum=num[1];
ans=0;
for(i=2;i<=n;i++)
{
ans+=sum*num[i];
sum+=num[i];//前i个石头的重量和;
}
printf("%lld\n",ans);
return 0;
}
🚩网络分析
??问题描述
?明正在做?个?络实验。他设置了n台电脑，称为节点，?于收发和存储数据。初始时，所有节点都是独?的，不存在任何连接。?明可以通过?线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在?线连接，称为相邻。?明有时会测试当时的?络，他会在某个节点发送?条信息，信息会发送到每个相邻的节点，之后这些节点?会转发到??相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。 ?条信息只存储?次。给出?明连接和测试的过程，请计算出每个节点存储信息的??。
【样例输入】
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1
【样例输出】
13 13 5 3
??思路分析
这一题用带权并查集， 用dis表示此节点与根节点的差值， 用value表示根的值，每次传值往根节点赋值。
- 操作1，并入一个集合，更新被并入的根的dis值等于两个value相减
- 操作2，find根节点，往根节点里赋值
// c
#include <stdio.h>
#define Maxn 10010
int A[Maxn];
int dis[Maxn];
int value[Maxn];
int find(int a)
{
if (A[a] != a) {
int temp = A[a];
A[a] = find(A[a]);
dis[a] += dis[temp];
}
return A[a];
}
int main()
{
int n, m, a ,b, i, fa, fb;
scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++) A[i] = i;
int flag;
for (i = 0 ; i < m; i++) {
scanf("%d", &flag);
if (flag == 1) {
scanf("%d%d", &a, &b);
fa = find(a);
fb = find(b);
if (fa != fb) {
A[fa] = fb;
dis[fa] = value[fa] - value[fb];
}
}else {
scanf("%d%d", &a, &b);
fa = find(a);
value[fa] += b;
}
}
for (i = 1; i <= n; i++) printf("%d ", value[find(i)] + dis[i]);//通过find更新dis值，最后输出
return 0;
}
🚩快乐司机
??问题描述
“嘟嘟嘟嘟嘟嘟
喇叭响
我是汽车小司机
我是小司机
我为祖国运输忙
运输忙”
这是儿歌“快乐的小司机”。话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土…
现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0<gi<=100,0<=pi<=100)
输入格式
输入第一行为由空格分开的两个整数n w
第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi
输出格式
最大价值（保留一位小数）样例输入
5 36
99 87
68 36
79 43
75 94
7 35样例输出
71.3
??思路分析
每次应选取单位重量价值最大的物品进行装载，才能求出汽车装载的最大价值，所以考虑求出每个物品的单价，并进行从高到低排序。
- 1.用一个数据结构将一个物品的重量、价值及单价存起来，并将单价进行排序；
- 2.如果一个物品的重量g[i].g>w，则说明这是最后一件能装载的货物，且装的重量最多为w。
- 3.如果一个物品的重量g[i].g<w，则将这个物品全部带走，并且w减少重量g[i].g。
??代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct good{
double g,p,ave;
}g[10005];
bool cmp(good g1,good g2)
{
return g1.ave>g2.ave;
}
int main()
{
int n,w;
scanf("%d%d",&n,&w);
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&g[i].g,&g[i].p);
g[i].ave=g[i].p/g[i].g;
}
sort(g,g+n,cmp);
double ans=0;
while(w)
{
for(int i=0;i<n;i++)
{
if(g[i].g>=w)//如果物品的重量大于w，也就是说这是能装载的最后一件物品
{
ans+=w*g[i].ave;
w=0;
}
else//如果物品的重量小于w，则全部带走
{
ans+=g[i].p;
w-=g[i].g;
}
}
w=0;//所有货物都装完，还能装
}
printf("%.1f\n",ans);
return 0;
} 
🚩运输计划
??问题描述
公元2044年，人类进入了宇宙纪元。
L 国有?n?个星球，还有?n-1 条双向航道，每条航道建立在两个星球之间，这?n-1 条航道连通了?L?国的所有星球。
小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui??号星球沿最快的宇航路径飞行到 vi??号星球去。显然，飞船驶过一条航道是需要时间的，对于航道?jj，任意飞船驶过它所花费的时间为 tj?，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新，?L?国国王同意小?P?的物流公司参与?L?国的航道建设，即允许小P?把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了?m?个运输计划。在虫洞建设完成后，这?m?个运输计划会同时开始，所有飞船一起出发。当这?m?个运输计划都完成时，小?P?的物流公司的阶段性工作就完成了。
如果小?P?可以自由选择将哪一条航道改造成虫洞， 试求出小?P?的物流公司完成阶段性工作所需要的最短时间是多少？
输入样例
6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5输出样例
11
??思路分析
二分查找答案，二分判断条件是这条路径的长度都小于mid或者大于mid的路径用差分数组维护后求出每条线段被走过几次，走过次数等于大于mid的路径数的就是可以被更改的线段，然后再其中找到最大的那条，用最长路径 - 这个值，如果小于等于mid则成立。
??代码
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
inline int scan()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-')c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
const int maxn=3e5+5;
const int maxnbits=20;
int n,m,num,ret,Max,tol;
int depth[maxn],father[maxn][maxnbits],lg[maxn],dis[maxn],len[maxn],sum[maxn],head[maxn<<1];
struct edge{
int to;
int next;
int w;
}e[maxn<<1];
struct node{
int x,y;
}nd[maxn];
void add(int s,int t,int w){
tol++;
e[tol].to=t;
e[tol].next=head[s];
e[tol].w=w;
head[s]=tol;
}
int v[maxn];
void dfs(int nowp,int fa){
depth[nowp]=depth[fa]+1;
father[nowp][0]=fa;
for(int i=1;i<=lg[depth[nowp]]+1;i++){
father[nowp][i]=father[father[nowp][i-1]][i-1];
}
for(int i=head[nowp];i;i=e[i].next){
int to=e[i].to;
if(to!=fa){
dis[to]=dis[nowp]+e[i].w;
v[to]=e[i].w;
dfs(to,nowp);
}
}
}
int LCA(int a,int b){
if(depth[a]<depth[b]){
swap(a,b);
}
while(depth[a]!=depth[b]){
a=father[a][lg[depth[a]-depth[b]]];
}
if(a==b) return a;
for(int i=lg[depth[a]];i>=0;i--){
if(father[a][i]!=father[b][i]){
a=father[a][i];
b=father[b][i];
}
}
return father[a][0];
}
void DFS(int nowp,int fa){
for(int i=head[nowp];i;i=e[i].next){
int to=e[i].to;
if(to!=fa){
DFS(to,nowp);
sum[nowp]+=sum[to];///从叶子节点进行求前缀和
}
}
if(sum[nowp]==num){///sum[nowp]是nowp点的边被num条路径走过几次，如果走过次数等于num，则可对这条边进行更改
ret=max(ret,v[nowp]);///记录可更改最大边
}
}
bool check(int mid){
num=0;
ret=0;
memset(sum,0,sizeof(sum));
for(int i=0;i<m;i++){
if(len[i]>mid){///这条路径是否比mid大，如果大，则可对其的某跳边进行更改
num++;
int lca=LCA(nd[i].x,nd[i].y);
sum[nd[i].x]++,sum[nd[i].y]++,sum[lca]-=2;///差分记录这条路径的所有边可进行更改
}
}
if(!num) return true;///如果没有比mid大的路径，那么它就是合法路径（mid）
DFS(1,0);///否则对能更改的路径进行更改
return Max-ret<=mid;///如果最长路径-能更改的最大边小于等于mid，则这个mid合法
}
int main(){
lg[0]=-1;
for(int i=1;i<maxn-2;i++){
lg[i]=lg[i>>1]+1;
}
int a,b,t;
int l=0,r=-1;
n=scan();
m=scan();
for(int i=0;i<n-1;i++){
a=scan();
b=scan();
t=scan();
add(a,b,t);
add(b,a,t);
}
dfs(1,0);
for(int i=0;i<m;i++){
a=scan();
b=scan();
nd[i]={a,b};
int lca=LCA(a,b);
len[i]=dis[a]+dis[b]-2*dis[lca];///计算a-b的距离
r=max(r,len[i]);///查找最大的路径长度，做二分最大值
Max=r;
}
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){///如果这个mid符合条件，则找更小的，看能否找到符合条件的
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
printf("%d\n",ans);
return 0;
}
🍺🍺🍺
?🌟🌟 给大家推荐一个在线编译工具：Dotcpp在线编译?🌟🌟
🍺🍺🍺
🍊🍊🍊
总结不易，看到这那就来个三连吧，肝。。。🍺🍺🍺
🍊🍊🍊
署名：左手の明天
?
