This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const long long INF = 2e18 + 5;
int n, k, a, b, c;
long long l, r, m, park[N], nongood[N];
bool ispark[N];
vector<pair<int, long long>> tree[N];
void dfs(int v, int p, int pw, long long x){
if(tree[v].size() == 1) nongood[v] = 0;
for(auto e : tree[v]){
if(e.first != p){
dfs(e.first, v, e.second, x);
park[v] = min(park[v], park[e.first] + e.second);
}
}
for(auto e : tree[v]){
if(e.first != p){
if(nongood[e.first] + e.second + park[v] > x){
nongood[v] = max(nongood[v], nongood[e.first] + e.second);
}
}
}
if(park[v] > x) nongood[v] = max(nongood[v], 0ll);
if(nongood[v] + pw > x) ispark[v] = true, park[v] = 0, nongood[v] = -INF;
}
bool check(long long x){
memset(ispark, 0, sizeof(ispark)), fill(park, park + N, INF), fill(nongood, nongood + N, -INF);
dfs(1, 0, 0, x);
if(park[1] > x) ispark[1] = true;
return accumulate(ispark + 1, ispark + n + 1, 0) <= k;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n - 1; i++){
cin >> a >> b >> c;
tree[a].push_back({b, c});
tree[b].push_back({a, c});
}
l = -1, r = INF;
while(r - l > 1){
m = l + (r - l) / 2;
if(check(m)) r = m;
else l = m;
}
check(r);
vector<int> v;
for(int i = 1; i <= n; i++) if(ispark[i]) v.push_back(i);
for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);
cout << r << "\n";
for(auto i : v) cout << i << " ";
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:77:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
77 | for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);
| ~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |