| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315423 | DangerNoodle7591 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define int long long int
#define N 20000
#define big 1000000000000000000
#define p push
#define f first
#define s second
#define pb push_back
#define ins insert
int n,k;
vector<pair<int,int>> adj[N];
int sub[N];
int center[N];
int cev=big;
void dfs(int x,int baba){
sub[x]=1;
for(auto u:adj[x]){
if(u.f==baba||center[u.f]==1)continue;
dfs(u.f,x);
sub[x]+=sub[u.f];
}
}
int bul(int x,int hed,int once){
for(auto u:adj[x]){
if(center[u.f]||once==u.f)continue;
if(sub[u.f]>hed/2)return bul(u.f,hed,x);
}
return x;
}
vector<pair<int,int>> v;
void mes(int x,int once,int uzak,int kac){
if(uzak<=k)v.pb({uzak,kac});
for(auto u:adj[x]){
if(u.f==once||center[u.f])continue;
mes(u.f,x,uzak+u.s,kac+1);
}
}
void solve(int x){
dfs(x,-1);
int centroid=bul(x,sub[x],-1);
//cout<<centroid<<"_"<<endl;
center[centroid]=1;
set<pair<int,int>> yol;
yol.ins({0,0});
for(auto u:adj[centroid]){
if(center[u.f])continue;
v.clear();
mes(u.f,centroid,u.s,1);
for(auto u:v){
int deg=k-u.f;
auto uu=yol.lower_bound({deg,-1});
if(uu==yol.end())continue;
if((*uu).f==deg){
cev=min(cev,u.s+(*uu).s);
}
}
for(auto u:v){
yol.ins(u);
}
}
for(auto u:adj[centroid]){
if(center[u.f]==0){
solve(u.f);
}
}
}
signed main(){
lalala;
cin>>n>>k;
vector<pair<int,int>> of;
for(int i=0;i<n-1;i++){
int x,y;cin>>x>>y;
of.pb({x,y});
}
for(int i=0;i<n-1;i++){
int c;cin>>c;
adj[of[i].f].pb({of[i].s,c});
adj[of[i].s].pb({of[i].f,c});
}
solve(0);
if(cev==big)cev=-1;
cout<<cev<<endl;
}