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
| #include <bits/stdc++.h>
#define pii pair<int,int>
#define MAX_N 200000
#define MAX_K 1000000
using namespace std;
const int INF = 1e9;
int n, k;
vector<pii> adj[MAX_N + 1];
unordered_set<int> init;
bool vis[MAX_N + 1];
int sz[MAX_N + 1];
int cost[MAX_K + 1];
int getSize(int u, int p) {
sz[u] = 1;
for(auto& [v, w] : adj[u]) {
if(!vis[v] and v != p)
sz[u] += getSize(v, u);
}
return sz[u];
}
int getCent(int u, int p, int size) {
for(auto& [v, _] : adj[u]) {
if(!vis[v] and v != p and sz[v] * 2 > size)
return getCent(v,u,size);
}
return u;
}
int solve(int p, int u, int weight, int path) {
int res = INF;
if(weight > k) return res;
res = min(res, cost[k-weight] + path);
for(auto& [v, w]: adj[u]) {
if(!vis[v] and v != p)
res = min(res, solve(u,v,weight + w, path + 1));
}
return res;
}
void update(int p, int u, int weight, int path) {
if(weight > k) return;
init.insert(weight);
cost[weight] = min(cost[weight], path);
for(auto& [v, w] : adj[u]) {
if(!vis[v] and v != p)
update(u,v,weight + w, path + 1);
}
}
int dnc(int u) {
int size = getSize(u, -1);
int cent = getCent(u, -1, size/2);
int res = INF;
vis[cent] = true;
for(auto& i : init) cost[i] = INF;
init.clear();
cost[0] = 0;
for(auto& [v, w] : adj[cent]) {
if(!vis[v]) {
res = min(res, solve(cent, v, w, 1));
update(cent, v, w, 1);
}
}
for(auto& [v, _] : adj[cent]) {
if(!vis[v])
res = min(res, dnc(v));
}
return res;
}
int main() {
cin>>n>>k;
for(int i = 1, u, v, w; i < n; i++) {
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
for(int i = 0; i <= k; i++) cost[i] = INF;
int res = dnc(0);
cout<<(res == INF ? -1 : res);
return 0;
}
|
