Luogu P4149 [IOI2011]Race

题目链接：​​传送门​​

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int next, to, w;
}e[A];
int head[A], num;
void add(int fr, int to, int w) {
  e[++num].next = head[fr];
  e[num].to = to;
  e[num].w = w;
  head[fr] = num;
}
int n, m, k, a, b, c, G, tot, cnt, ans = INT_MAX;
int siz[B], dep[B], dis[B], cc[B], vis[B], f[A], mx[B];
void getG(int fr, int fa) {
  siz[fr] = 1; mx[fr] = 0;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa or vis[ca]) continue;
    getG(ca, fr);
    siz[fr] += siz[ca];
    mx[fr] = max(mx[fr], siz[ca]);
  }
  mx[fr] = max(mx[fr], tot - siz[fr]);
  G = mx[fr] < mx[G] ? fr : G;
}
void dfs(int fr, int fa, int dist, int bs) {
  if (dist > k) return;
  dep[++cnt] = dist; cc[cnt] = bs;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (ca == fa or vis[ca]) continue;
    dfs(ca, fr, dist + e[i].w, bs + 1);
  }
}
void calc(int fr) {
  f[0] = 0; cnt = 0;
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (vis[ca]) continue;
    int size = cnt;
    dfs(ca, fr, e[i].w, 1);
    for (int j = size + 1; j <= cnt; j++) ans = min(ans, f[k - dep[j]] + cc[j]);
    for (int j = size + 1; j <= cnt; j++) f[dep[j]] = min(f[dep[j]], cc[j]);
  }
  for (int i = 1; i <= cnt; i++) f[dep[i]] = 0x3f3f3f3f;
}
void divide(int fr) {
  vis[fr] = 1; calc(fr);
  for (int i = head[fr]; i; i = e[i].next) {
    int ca = e[i].to;
    if (vis[ca]) continue;
    tot = siz[ca]; G = 0; getG(ca, fr);
    divide(G);
  }
}
inline char GETCHAR() {
  static char buf[1000], *p1 = buf, *p2 = buf;
  return p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 1000, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> void read(T &x) {
  x = 0; char ch = GETCHAR();
  while (!isdigit(ch)) ch = GETCHAR();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = GETCHAR();
}

int main(int argc, char const *argv[]) {
  scanf("%d%d", &n, &k); memset(f, 0x3f, sizeof f);
  for (int i = 2; i <= n; i++) {
    read(a); read(b); read(c); a++; b++;
    add(a, b, c); add(b, a, c);
  }
  tot = mx[0] = n; getG(1, 0);
  divide(G);
  printf("%d\n", (ans > n) ? -1 : ans);
  return 0;
}