#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update
>;
// indexed_set<int> s;
// and use s.insert(x), s.erase(x),
// *s.find_by_order(k), s.order_of_key(x), etc.
using ll = long long;
vector<pair<int ,unsigned int>> adj[10001];
int n , k , x , ek , dui , siz[10001];
unsigned int one[10001][10001] , two[10001][10001] , c , uno , dos;
void getans( int me , int par ) {
siz[me] = 1;
one[me][1] = 0;
two[me][1] = 0;
for( int z = 0; z < (int)adj[me].size(); z++ ) {
if( adj[me][z].first != par ) {
getans( adj[me][z].first , me );
siz[me] += siz[adj[me][z].first];
for( int zz = min( k , siz[me]); zz > 1; zz-- ) {
for( int y = min( zz - 1 , siz[adj[me][z].first]) ; y > 0; y-- ) {
c = one[me][zz - y] + one[adj[me][z].first][y] +
((ll)2 * adj[me][z].second);
one[me][zz] = min( one[me][zz] , c );
c = min( two[me][zz - y] + one[adj[me][z].first][y] +
(2 * adj[me][z].second) , one[me][zz - y] + two[adj[me][z].first][y] + adj[me][z].second );
two[me][zz] = min( two[me][zz] , c );
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> x;
for( int z = 1; z < n; z++ ) {
cin >> ek >> dui >> c;
adj[ek].push_back({dui , c});
adj[dui].push_back({ek , c});
}
for( int z = 0; z <= n; z++ ) {
for( int y = 0; y <= n; y++ ) {
one[z][y] = 200000000;
two[z][y] = 200000000;
}
}
getans( x , 0 );
cout << min( one[x][k] , two[x][k] ) << "\n";
return 0;
}
# | 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... |