# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1144060 | pedreitorzelda | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<bool>vis;
vector<map<ll,ll>>nodes;
vector<vector<pair<ll,ll>>>g;
vector<ll>dist_way;
vector<ll>dist_cant;
ll n,k;
ll cur_ans = int(1e9);
void dfs(ll u){
if(vis[u])return;
vis[u]=true;
for(auto it : g[u]){
if(!vis[it.first]){
dfs(it.first);
ll son = it.first;
if(nodes[son].size()>nodes[u].size()){
swap(nodes[u],nodes[son]);
}
for(auto it2 : nodes[son]){
cout << u << " - " << son<<" :"<< k+2*dist_way[u]-it2.first << " " << k << " " << dist_way[u] << " " << it2.first << endl;
if(nodes[u].find(k+2*dist_way[u]-it2.first)!=nodes[u].end()){
cur_ans = min(cur_ans, nodes[u][k+2*dist_way[u]-it2.first]+it2.second-2*dist_cant[u]);
}
}
for(auto it2 : nodes[son]){
if(nodes[u].find(it2.first)==nodes[u].end())nodes[u][it2.first]=it2.second;
else nodes[u][it2.first] = min(nodes[u][it2.first],it2.second);
}
}
}
return;
}
void prep_dfs(int u){
if(vis[u])return;
vis[u]=true;
nodes[u][dist_way[u]]=dist_cant[u];
for(auto it : g[u]){
if(!vis[it.first]){
dist_way[it.first]=dist_way[u]+it.second;
dist_cant[it.first]=dist_cant[u]+1;
prep_dfs(it.first);
}
}return;
}
int best_path(int N, int K,int H[][2], int L[]){
if(k==1){return 0;}
nodes.resize(N+2);
vis.resize(N+2,0);
g.resize(N+2);
dist_way.resize(N+2,0);
dist_cant.resize(N+2,0);
n=N,k=K;
cur_ans = -1;
for(ll i=0;i<N-1;i++){
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
prep_dfs(0);
for(int i=0;i<=n;i++)vis[i]=0;
dfs(0);
nodes.clear();
vis.clear();
g.clear();
dist_way.clear();
dist_cant.clear();
if(cur_ans==1e9)cur_ans = -1;
return cur_ans;
}
signed main(){
ll t;
cin >> t;
while(t--){
int n,k;
cin >> n >> k;
int H[n][2];
int L[n];
for(int i=0;i<n-1;i++){
for(int j=0;j<2;j++){
cin >> H[i][j];
}
}
for(int i=0;i<n-1;i++)cin >> L[i];
cout << best_path(n,k,H,L) << endl;
}
return 0;
}