RT,先放代码
#include<bits/stdc++.h>
#define max(A,B) (A<B?B:A)
#define min(A,B) (A>B?B:A)
#define bug cout<<"I AK IOI"<<endl;
#define gc getchar
using namespace std;
const int N=6e4+1;
inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline int read(){int res = 0, f = 0; char ch = gc();for(; !isdigit(ch); ch = gc()) f |= (ch == '-'); for(;isdigit(ch);ch=gc()) res = (res << 1) + (res << 3) + (ch ^ '0');return f ? -res :res;}
struct node{
int nxt,to,qz;
}e[N*2];int cnt,head[N];
inline void add(int a,int b,int c){e[++cnt].to=b,e[cnt].qz=c,e[cnt].nxt=head[a],head[a]=cnt;}
int n,m,a,b,c,qwq;
int jis=0;
multiset<int > vec[N*2];
inline int dfs(int k,int x,int fa,int kkk)
{
vec[kkk].clear();
for(int i=head[x];i;i=e[i].nxt)
{
int nxt=e[i].to; if(nxt==fa) continue ;
int jil=dfs(k,nxt,x,nxt)+e[i].qz;
if(jil>=k) jis++;
else vec[kkk].insert(jil);
}
int Max=0;
while(!vec[kkk].empty())
{
auto i=vec[kkk].begin();
auto it=vec[kkk].lower_bound(k-*i);
if(it==vec[kkk].begin() && vec[kkk].count(*it)==1) it++;
if(it!=vec[kkk].end()){
jis++;
vec[kkk].erase(it);
vec[kkk].erase(vec[kkk].begin());
// vec[kkk].erase(vec[kkk].begin());
// vec[kkk].erase(it);
} else Max=max(Max,*i),vec[kkk].erase(i);
}
return Max;
}
signed main(){
n=read(),m=read();
for(int i=1;i<n;i++){a=read(),b=read(),c=read();add(a,b,c),add(b,a,c);}
jis=0;
int l=1,r=5e8+1,mid,Max=-1;
while(l<r){
qwq=0;
jis=0;
mid=(l+r)>>1;
int zzx=dfs(mid,1,0,1);
if(jis>=m) Max=max(Max,mid),l=mid+1;
else r=mid-1;
}
qwq=0;
jis=0;
int zzx=dfs(l,1,0,1);
if(jis>=m) Max=max(Max,l);
cout<<Max;
}
在本代码中
vec[kkk].erase(it);
vec[kkk].erase(vec[kkk].begin());
// vec[kkk].erase(vec[kkk].begin());
// vec[kkk].erase(it);
这一段,上下两边的区别是下边RE70分,上边AC,为啥啊?难道不等价吗?it是不可能等于begin的