Submission #2067938

---

Source Code Expand

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
typedef pair<P,int> PP;
int n,L;
vector<vector<PP> > G;
vector<vector<P> >D;
vector<int> C;

int dfs1(int pos,int pre){
  for(auto p:G[pos]){
    int to,cost;
    tie(to,cost) = p.first;
    if(to == pre) continue;
    D[pos].push_back(P(cost+dfs1(to,pos),to));
  }
  if(D[pos].size() == 0) D[pos].push_back(P(0,-1));
  sort(D[pos].begin(),D[pos].end(),greater<P>());
  
  return D[pos][0].first;
}

void dfs2(int pos,int pre){
  if(D[pos].size() == 0) D[pos].push_back(P(0,-1));
  
  auto Push=[&](int to,int cost){
    int a = D[pos][0].second;
    D[to].push_back(P(D[pos][to == a].first+cost,pos));
    sort(D[to].begin(),D[to].end(),greater<P>());
  };

  for(auto p:G[pos]){
    int to,cost;
    tie(to,cost) = p.first;
    if(to == pre) continue;
    Push(to,cost);
    dfs2(to,pos);
  }
}


int dfs3(int pos,int pre=-1){
  if(pre != -1 && G[pos].size() == 1) return C[pos] = 0;
  int res = 0;
  for(auto p:G[pos]){
    int to = p.first.first;
    int dir = p.second;
    if(to == pre) continue;
    res += (dir == 0) + dfs3(to,pos);
  }
  return C[pos] = res;
}

int dfs4(int pos,int pre){
  auto update=[&](int to,int dir){
    C[to] = dir == 0? C[pos]-1:C[pos]+1;
  };

  int res = D[pos][0].first<=L? C[pos]:INF;  
  for(auto p:G[pos]){
    int to = p.first.first;
    int dir = p.second;
    if(to == pre) continue;
    update(to,dir);
    Min(res,dfs4(to,pos));
  }
  return res;
}

signed main(){
  cin>>n>>L;
  G.resize(n);
  D.resize(n);
  C.resize(n);
  for(int i=0;i<n-1;i++){
    int a,b,c;
    cin>>a>>b>>c; a--,b--;
    G[a].push_back(PP(P(b,c),0));
    G[b].push_back(PP(P(a,c),1));
  }

  dfs1(0,-1);
  dfs2(0,-1);
  dfs3(0,-1);
  int ans = dfs4(0,-1);
  if(ans == INF) ans = -1;
  cout<<ans<<endl;

  return 0;
}

Submission Info

Judge Result