#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define sz size()
#define pb push_back
const int N = 2e5;
ll n,k;
//int H[N+1][2],L[N+1];
vector<pii> g[N+1];
ll dw[N+1],d[N+1];
set<pii> st[N+1];
ll ans=1e9;
void calc(int v,int pr){
for(auto [to,w]: g[v]){
if(to!=pr){
dw[to]=dw[v]+w;
d[to]=d[v]+1;
calc(to,v);
}
}
}
void dfs(int v,int pr){
st[v].insert({dw[v],v});
for(auto [to,w]: g[v]){
if(to!=pr){
dfs(to,v);
if(st[v].sz<st[to].sz)
st[v].swap(st[to]);
for(auto [D,j]: st[to]){
ll x=k+2*dw[v]-D;
auto it=st[v].lower_bound({x,0});
if(it!=st[v].end() && it->fi==x){
ans=min(ans,d[j]+d[it->se]-2*d[v]);
}
}
for(auto j: st[to]){
st[v].insert(j);
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
//void solve(){
//cin>>n>>k;
k=K;
for(int i = 1; i <= n-1; i++){
//cin>>H[i][0]>>H[i][1]>>L[i];
H[i][0]++,H[i][1]++;
g[H[i][0]].pb({H[i][1],L[i]});
g[H[i][1]].pb({H[i][0],L[i]});
}
calc(1,-1);
dfs(1,-1);
/*
for(int i = 1; i <= n; i++){
cout<<i<<": ";
for(auto j: st[i]){
cout<<"{"<<j.fi<<" "<<j.se<<"} ";
}
cout<<"\n";
}
*/
if(ans==1e9)
ans=-1;
//cout<<ans<<"\n";
return ans;
}
/*
int main(){
solve();
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... |