记录编号	391139	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.481 s
提交时间	2017-04-05 10:33:16	内存使用	18.03 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <functional>
#include <bitset>
using namespace std;
#define MAXN 200003
int n, k;
int size[MAXN];
int wei[MAXN], deep[MAXN];
int root, div_size;
bool vis[MAXN];
struct edge{
  int to, cost, next;
}es[MAXN<<1];
int head[MAXN], _etot;
inline void addedge(int u, int v, int c){
  es[++_etot] = (edge){v, c, head[u]}; head[u] = _etot;
  es[++_etot] = (edge){u, c, head[v]}; head[v] = _etot;
}
void get_root(int u, int f){
  size[u] = 1;
  int son = 0;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to;
    if(to != f && !vis[to]){
      get_root(to, u);
      size[u] += size[to];
      if(size[son] < size[to])son = to;
    }
  }
  wei[u] = max(size[son], div_size-size[son]);
  if(wei[root] > wei[u])root = u;
}
int dist[MAXN], dfs_dist[MAXN], cur[MAXN], cnt;
void dfs(int u, int f, int d){
  dfs_dist[++cnt] = dist[u];
  cur[cnt] = d;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to;
    if(to == f || vis[to])continue;
    dist[to] = dist[u] + es[i].cost;
    if(dist[to] > k)continue;
    dfs(to, u, d+1);
  }
}

int vis_tim;
int visk[1000001], cntk[1000001];
int ans = 2e9;
void calc(int u){
  vis_tim++;
  dist[u] = 0;
  cntk[0] = 0, visk[0] = vis_tim;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to;
    if(vis[to])continue;
    dist[to] = dist[u]+es[i].cost;
    if(dist[to] > k)continue;
    cnt = 0;
    dfs(to, 0, 1); 
    for(int j = 1; j <= cnt; j++){
      if(visk[k-dfs_dist[j]] != vis_tim){
        cntk[k-dfs_dist[j]] = 2e8;
        visk[k-dfs_dist[j]] = vis_tim;
      }
      ans = min(ans, cur[j]+cntk[k-dfs_dist[j]]);
    }
    for(int j = 1; j <= cnt; j++){
      if(visk[dfs_dist[j]] != vis_tim){
        cntk[dfs_dist[j]] = 2e8;
        visk[dfs_dist[j]] = vis_tim;
      }
      cntk[dfs_dist[j]] = min(cntk[dfs_dist[j]], cur[j]);
    }
  }
}
void solve(int u){
  vis[u] = true;
  calc(u);
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to;
    if(!vis[to]){
      root = 0; div_size = size[to];
      get_root(to, 0);
      solve(root);
    }
  }
}
int main(){
  int __size__ = 128<<20;
  char *__ptr__ = (char *)malloc(__size__)+__size__;
  __asm__("movl %0, %%esp\n"::"r"(__ptr__));
 // freopen("test_data.txt", "r", stdin);
  freopen("ioi2011-race.in", "r", stdin);
  freopen("ioi2011-race.out", "w", stdout);
  scanf("%d %d", &n, &k);
  for(int i = 1; i < n; i++){
    int u, v, c; scanf("%d %d %d", &u, &v, &c);
    u++, v++; addedge(u, v, c);
  }
  root = 0; wei[0] = 2e9; div_size = n;
  get_root(1, 0);
  solve(root);
  if(ans >= n)puts("-1");
  else printf("%d\n", ans);
  return 0;
}