| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1300234 | ammmiiiiinnnn | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=2e5+10;
const int maxk=1e6+10;
vector<pair<int,int>>adj[maxn];
bool mark[maxn];
int yal[maxn];
int sz[maxn];
int n,k;
int ans=1e6;
const int inf=1e7;
pair<int,int>et[maxn];
int global[maxk];
vector<int>modi;
vector<int>subtree;
int s(int u,int p){
sz[u]=1;
for(auto v:adj[u]){
int vv=v.first;
if(vv!=p && !mark[vv]){
s(vv,u);
sz[u]+=sz[vv];}}
return sz[u];}
int cen(int u,int p,int to){
for(auto v:adj[u]){
int vv=v.first;
if(vv!=p && !mark[vv]){
if(sz[vv]>to/2){
return cen(vv,u,to);
}}}
return u;}
void dfs(int u,int par){
subtree.push_back(u);
for(auto v:adj[u]){
int vv=v.first;
if(!mark[vv] && vv!=par){
et[vv]={et[u].first+1,et[u].second+yal[v.second]};
dfs(vv,u);}}
}
void solve(int u){
int siz=s(u,-1);
int cent=cen(u,-1,siz);
mark[cent]=1;
for(auto v:adj[cent]){
int vv=v.first;
int w=yal[v.second];
if(!mark[vv]){
et[vv]={1,w};
dfs(vv,-1);
for(int node:subtree){
int target=k-et[node].second;
if(target>=0 && global[target]!=inf){
ans=min(ans,global[target]+et[node].first);}}
for(int node:subtree){
int wh=et[node].second;
global[wh]=min(global[wh],et[node].first);
modi.push_back(wh);}
subtree.clear();
}}
for(int x:modi){
global[x]=inf;}
modi.clear();
for(auto v:adj[u]){
int vv=v.first;
if(!mark[vv]){
solve(vv);}}
}
int main(){
cin>>n>>k;
int u,v;
for(int i=0;i<=k;i++){
global[i]=inf;}
mark[n]=0;
for(int i=0;i<n-1;i++){
mark[i]=0;
cin>>u>>v;
adj[u].push_back({v,i});
adj[v].push_back({u,i});}
for(int i=0;i<n-1;i++){
cin>>v;
yal[i]=v;}
solve(0);
if(ans==1e6){
cout<<-1;}else{
cout<<ans;}
}