A
看样例猜做法
首先看看题目思索几秒应该和差分数组有关
然后拿差分数组试了一下样例，猜了一个做法
再自己构造了一下数据，好像是可以过的样子
对拍对拍！哦豁我不会写暴力啊orz，还好没出错orzorzorz,不过评测的时候着实有点慌
B
一开始没看题面，以为是一个面值拿其他俩面值表示就可以了，想了想，对！EX_gcd，敲了30~40min,小样例过了，大样例过过过过...唉握草？？！最后一个点怎么回事
哎握草？？！！！！它一个数是拿另外三个数表示的！！！
我人傻了.JPEG
最后才想起来，它是背包啊是背包，还是最简单的那种无限背包（背包问题1.......），f数组甚至是bool类型的那种背包
C
emmm，没啥想法的一道题
方法过于难以描述，将在最后放上代码，其中上下均///////的表示在写题中没有注意到的错误（还挺多的）
老板说的对，这道题满分不好拿，但是由于数据分段给的非常清楚，要混上个40，50分是轻轻松松的，而我WA0确实是不应该（随便敲一个树的直径都有20分）
总结一下
期望得分：(100 + 100 +０ = 200)
实际得分：(100 + 100 + 0 = 200)
没有什么大的智障失误，不过WA0是非常不应该的
最后放上C题AC代码
#include<stdio.h>
#include<bits/stdc++.h>
#define LL long long
#define maxn 50005
#define maxm 100005
#define rel(i,s,n) for(int i=(s);i<(n);i++)
#define rep(i,s,n) for(int i=(s);i<=(n);i++)
#define red(i,s,n) for(int i=(s);i>=(n);i--)
#define res(i,x) for(int i=Last[x];i;i=Next[i])
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<class T> inline void read(T &n){
char ch=GC;T w=1,x=0;
while(!isdigit(ch)){if(ch=='-') w=-1;ch=GC;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=GC;}
n=x*w;
}
int x,y,z;
int L,R,Mid;
int n,m,tot,Ans;
struct Phenning{int id;int val;bool MK;};
int End[maxm],Last[maxn],Next[maxm],Len[maxm],f[maxn],g[maxn];
vector<Phenning>Son[maxn];
bool cmp(Phenning a, Phenning b){
return a.val < b.val;
}
void add(int x, int y, int z){
tot ++;
Next[tot] = Last[x];
Last[x] = tot;
End[tot] = y;
Len[tot] = z;
}
void QwQ(int x, int fa){
int son = 0;
res(i,x)if(End[i]!=fa){
son ++;
QwQ(End[i], x);
///////////////!!!!!!!!!!!!!!!!!!!!!
f[x]+=f[End[i]];
///////////////!!!!!!!!!!!!!!!!!!!!!
Phenning tmp;
tmp.MK = 0;
tmp.id = End[i];
tmp.val = Len[i] + g[End[i]];
Son[x].push_back(tmp);
}
if(son == 0)return;
son --;
sort(Son[x].begin(), Son[x].end(), cmp);
rep(i, 0, son)if(Son[x][i].val >= Mid){f[x] ++; Son[x][i].MK = 1; continue;}
rep(i, 0, son){
//////////////////////////
if(Son[x][i].MK) continue;
//////////////////////////
Phenning tmp;
tmp.val = Mid - Son[x][i].val;
int pos = lower_bound(Son[x].begin()+i+1, Son[x].end(), tmp, cmp) - Son[x].begin();
if(pos>son)continue;
while(Son[x][pos].MK == 1 && pos < son)pos ++;
///////////////////////////
if(Son[x][pos].MK == 1)continue;
///////////////////////////
if(Son[x][pos].val >= tmp.val){f[x] ++; Son[x][i].MK = Son[x][pos].MK = 1;}
}
red(i, son, 0)if(!Son[x][i].MK){g[x] = Son[x][i].val;break;}
///////////////
Son[x].clear();
///////////////
}
bool isok(){
rep(i, 1, n)f[i] = g[i] = 0;
QwQ(1, 0);
if(f[1] >= m)return 1;
//puts("hahhahaha");
return 0;
}
int main(){
read(n);read(m);
rel(i, 1, n){
read(x);read(y);read(z);
R += z;
add(x, y, z);
add(y, x, z);
}
while(L <= R){
Mid = (L + R) >> 1;
if(isok())Ans = Mid, L = Mid + 1;
else R = Mid - 1;
}
printf("%d", Ans);
return 0;
}
//长度最小的赛道长度最大:二分