Submission #2067081

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

struct edge
{
  int to, cost;
  bool type;
};

int N, D;
vector< edge > g[100000];
int max_dist[100000];
int change[100000];

void dfs(int idx, int par)
{
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    dfs(e.to, idx);
    max_dist[idx] = max(max_dist[idx], max_dist[e.to] + e.cost);
    change[idx] += change[e.to];
    change[idx] += e.type;
  }
}

int ans = -1;

void dfs2(int idx, int par, int dist, int come)
{
  vector< pair< int, int > > curr_dist{{dist, -1}};
  int need = come;
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    curr_dist.emplace_back(max_dist[e.to] + e.cost, e.to);
    need += change[e.to];
    need += e.type;
  }
  sort(curr_dist.rbegin(), curr_dist.rend());

  if(curr_dist[0].first <= D) {
    if(~ans) ans = min(ans, need);
    else ans = need;
  }
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    dfs2(e.to, idx, curr_dist[curr_dist[0].second == e.to].first + e.cost, need - change[e.to] + (e.type ? -1 : 1));
  }
}


int main()
{
  cin >> N >> D;
  for(int i = 0; i < N - 1; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x, --y;
    g[x].emplace_back((edge) {y, z, true});
    g[y].emplace_back((edge) {x, z, false});
  }

  int root = -1;
  for(int i = 0; i < N; i++) {
    if(g[i].size() >= 2) root = i;
  }

  if(root == -1) {
    if(g[0][0].cost > D) cout << -1 << endl;
    else cout << 0 << endl;
    return (0);
  }

  dfs(0, -1);
  dfs2(0, -1, 0, 0);
  cout << ans << endl;
}

Submission Info

Judge Result