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
| #include <cstdio>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, M = N << 1;
struct Node
{
LL s;
int t;
friend Node operator+(const Node &x, const Node &y)
{
return (Node){x.s + y.s, x.t + y.t};
}
friend Node operator+(const Node &x, const LL k)
{
return (Node){x.s + k, x.t};
}
friend Node max(const Node &x, const Node &y)
{
if (x.s > y.s || (x.s == y.s && x.t < y.t))
return x;
return y;
}
} f[N][3];
int n, m;
int idx, hd[N], nxt[M], edg[M], wt[M];
void dfs(int x, int fa, Node k)
{
for (int i = 0; i < 3; i++)
f[x][i].t = f[x][i].s = 0;
for (int i = hd[x]; ~i; i = nxt[i])
if (edg[i] != fa)
{
dfs(edg[i], x, k);
f[x][2] = max(f[x][2] + f[edg[i]][0], f[x][1] + f[edg[i]][1] + k + wt[i]);
f[x][1] = max(f[x][1] + f[edg[i]][0], f[x][0] + f[edg[i]][1] + wt[i]);
f[x][0] = f[x][0] + f[edg[i]][0];
}
f[x][0] = max(f[x][0], max(f[x][1] + k, f[x][2]));
}
void add(int a, int b, int c)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
wt[idx] = c;
}
int main()
{
scanf("%d%d", &n, &m);
m++;
for (int i = 1; i <= n; i++)
hd[i] = -1;
for (int i = 1, u, v, w; i < n; i++)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
LL l = -3e11, r = 3e11, res;
while (l <= r)
{
LL mid = l + r >> 1;
dfs(1, 0, (Node){-mid, 1});
f[1][0].t <= m ? (res = f[1][0].s + m * mid, r = mid - 1) : l = mid + 1;
}
printf("%lld", res);
return 0;
}
|