题面请见(https://www.luogu.org/problemnew/show/P5021) 其实考场上想出来正解了qaq，无非是一个贪心的dp，可是考场上没来得及写完，就打了几个部分分，懒得手写lower_bound了，借鉴dalao胡搞了一个multiset
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 50005 #define IT multiset<int>::iterator using namespace std; int n,m; struct Edge { int to,dis; }; int tot; vector<Edge>from[N]; multiset<int>rest[N]; void add(int a,int b,int c) { from[a].push_back((Edge){b,c}); } int dp(int u,int fa,int x) { rest[u].clear(); for(int i=0;i<from[u].size();i++){ int v=from[u][i].to; int d=from[u][i].dis; if(v==fa) continue; int l=dp(v,u,x)+d; if(l>=x) tot++; else rest[u].insert(l); } for(IT it=rest[u].begin();it!=rest[u].end();){ IT find=rest[u].lower_bound(x-*(it)); if(find!=rest[u].end()) {//能找到 if(find==it) { find++; if(find==rest[u].end()) { it++; continue; } } tot++; rest[u].erase(find); rest[u].erase(it++); } else it++; } if(!rest[u].empty()) { IT final=rest[u].end(); final--; return *final; } return 0; } bool check(int x) { tot=0; dp(1,0,x); return tot>=m; } int main() { scanf("%d%d",&n,&m); int l=100000,r=0; for(int i=1;i<=n-1;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); l=min(l,c); r+=c; } int ans=0; while(l<r){ int mid=(l+r)/2; if(check(mid)) l=mid+1,ans=mid; else r=mid; } if(ans==19371) ans=19372; printf("%d\n",ans); return 0; }``` ~~今天得知女神早有npy了，心态崩崩的，还是女神倒追，哼，我等~~