#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define ll long long
#define ld long double
#define int long long
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int MOD = 1e9+7 ;
//const int MOD = 998244353 ;
const int N = 1e5+5 ;
const ll INF = 1e18 ;
const ll MIN = -1e18 ;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void solve() {
ll n,k,x;cin>>n>>k>>x;
vector<pair<ll,ll>> g[n+1];
for(int i=1;i<n;i++){
ll u,v,c;cin>>u>>v>>c;
g[u].pb({v,c});
g[v].pb({u,c});
}
vector<vector<ll>> dp(n+1,vector<ll>(k+1,INF));
vector<ll> childs(n+1,1);
ll ans=INF;
function<void(int,int)> dfs=[&](int v,int p){
dp[v][1]=dp[v][0]=0;
for(auto [child,cost] : g[v]){
if(child == p)continue;
vector<ll> temp(k+1,INF);
for(int i=0;i<=min(k,childs[v]);i++){
temp[i]=dp[v][i];
}
for(int i=0;i<=min(k-1,childs[child]);i++){
temp[i+1]=min(temp[i+1],dp[child][i]+cost);
}
for(int i=1;i<=min(k,childs[v]);i++){
for(int j=0;j<=min(k,childs[child]) && j+i<=k;j++){
ll sum=i+j;
ll c=min(dp[v][i]*2+dp[child][j]+cost,(dp[child][j]+cost)*2+dp[v][i]);
temp[sum]=min(temp[sum],cost);
}
}
childs[v]+=childs[child];
for(int i=2;i<=min(k,childs[v]);i++){
dp[v][i]=min(dp[v][i],temp[i]);
}
}
};
dfs(x,0);
cout<<dp[x][k]<<endl;
}
signed main() {
FAST;
auto begin = std::chrono::high_resolution_clock::now();
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ll t=1;
cin>>t;
while(t--) solve();
#ifndef ONLINE_JUDGE
auto end = std::chrono::high_resolution_clock::now();
cout << setprecision(4) << fixed;
cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
#endif
}
Compilation message (stderr)
museum.cpp: In function 'int main()':
museum.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |