题意简述
给你一颗树有n(n<=5e4)个点，边权<=1e4。请你选出m(1<=m<n)条链，没有公共边，允许有公共点，使得$m$条链的边权和的最小值最大。
思路
二分+树上贪心检验
具体思路
首先二分是显然的，“最小值最大”是特点，而且显然有单调性。
关键在于，我们钦定了最小值mid之后，如何检验。其实我们只要能找出>=m条链使得最小值>=mid即珂。我们需要贪心。
（令根节点为1）
贪心策略
假设现在考虑以$u$为根的子树。对于$u$的每个儿子$v$，我们选择某一条到叶子节点的不带拐弯的链（后面会讲怎么选）。这条链的长度上传给$u$节点。此外，这个长度还要再加上$u$到$v$的边权长。设这个长度为val[v]。
那么，有两种情况我们能选出来一个满足条件的链：
- val[v]>=k，这条链不带拐弯
- 存在v1和v2使得val[v1]+val[v2]>=k，带一个拐弯
对于情况1，直接ans++即珂。
对于情况2，我们把除了情况1以外的val值放到一个multiset里面，记为s[u]。然后我们每次拿出最小的（即1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
如果能找到，先记录答案ans++，然后把这两个从s[u]中删除。
如果找不到怎么办呢？说明这个val即不满足val[v]>=k，也没有v2使得val[v1]+val[v2]>=k。那么，这个val就只能上传给u的父亲。如果最后s[u]中只剩下一个珂供选择，也是同样的道理，要作为选择上传给$u$的父亲。
在所有选剩下的节点中，我们显然要选长度最大的那一个给父亲。因为长度越大，越有珂能满足1和2条件中的一个。
#### 简略证明正确性（解决几个小问题）
1. 会不会有一个val[v1]，能找到匹配，但是直接上传到$u$的父亲比找一个$v2$匹配合算呢？
答案是不会。因为我们直接上传对答案的贡献也许是1（也许没有），还浪费了一个良好的匹配，也许以后就会匹配不上而导致答案不优；但是找匹配的话，不仅能弄一个1出来，匹配数和上面也是一样的。那就肯定更优。所以，我们的总体策略是对的
2. 匹配的问题：取val最小的，然后lowerbound找匹配，这样一定最优吗？
因为我们还要让失配的上传给$u$的父亲，而且要尽量大。所以我们肯定是省着点用，满足条件的里面选最小的即珂，这样能使留下来的最大，给父亲的就更有珂能找到更多满足条件的链。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
#define N 155555
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
class Graph
{
public:
int head[N];
int EdgeCount;
struct Edge
{
int To,Label,Next;
}Ed[N<<1];
void clear(int _V=N,int _E=N<<1)
{
memset(Ed,-1,sizeof(Edge)*(_E));
memset(head,-1,sizeof(int)*(_V));
EdgeCount=-1;
}
void AddEdge(int u,int v,int w=1)
{
Ed[++EdgeCount]=(Edge){v,w,head[u]};
head[u]=EdgeCount;
}
void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
int Start(int u) {return head[u];}
int To(int u){return Ed[u].To;}
int Label(int u){return Ed[u].Label;}
int Next(int u){return Ed[u].Next;}
}G;
void R1(int &x)
{
x=0;char c=getchar();int f=1;
while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=(f==1)?x:-x;
}
int n,m;
void Input()
{
R1(n),R1(m);
G.clear();
F(i,1,n-1)
{
int u,v,w;R1(u),R1(v),R1(w);
G.Add2(u,v,w);
}
}
int ans=0;
multiset<int> s[N];multiset<int>::iterator it;
int DFS(int u,int f,int k)
{
s[u].clear();
Tra(i,u) if (__v!=f)
{int v=__v;
int val=G.Label(i)+DFS(v,u,k);
if (val>=k) ++ans; //val>=k的直接处理掉情况1
else s[u].insert(val); //否则放到multiset里，处理情况2
}
int Max=0;//上传给u的父亲的最长的选剩下的链
while(!s[u].empty())
{
if (s[u].size()==1) //只剩一个了，直接处理掉
{
return max(Max,*s[u].begin());
}
it=s[u].lower_bound(k-(*s[u].begin()));if (it==s[u].begin() and s[u].count(*it)==1) ++it;
//找到和它不相等，和>=k，且最小的位置
if (it==s[u].end()) //找不到
{
Max=max(Max,*s[u].begin());
s[u].erase(s[u].begin());//那就相当于选剩下的，上传给u的父亲
}
else
{
++ans;s[u].erase(it);s[u].erase(s[u].begin());
//一个匹配：删掉两个，答案++
}
}
return Max;//把最大的上传给父亲
}
bool cxk(int mid)
{
ans=0;DFS(1,0,mid);
return ans>=m;
}
void Soviet()
{
int l=1,r=1e9;
while(l<r)
{
int mid=(l+r+1)>>1;
if (cxk(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
#define Flan void
Flan IsMyWife()
{
Input();
Soviet();
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();getchar();
return 0;
}