记录编号	600103	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	2.886 s
提交时间	2025-04-15 21:21:10	内存使用	10.89 MiB

#include <cstdio>

template <typename T>
T max(T x, T y) {
	return x > y ? x : y;
}

template <typename T>
T min(T x, T y) {
	return x < y ? x : y;
}

const int MAXN = 2e5 + 10;
const int MAXK = 1e6 + 10;

struct EDGE {
	int v, w, next;
	EDGE(){}
	EDGE(int v, int w, int next) : v(v), w(w), next(next) {};
} edge[MAXN << 1];

int head[MAXN], edgeNum;
void AddEdge(int u, int v, int w) {
	edge[++edgeNum] = EDGE(v, w, head[u]);
	head[u] = edgeNum;
}

int siz[MAXN], sum;
bool del[MAXN];
void CalcSumAndSiz(int root, int fa) {
	siz[root] = 1;
	sum++;
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v;
		if (v == fa || del[v]) continue;
		CalcSumAndSiz(v, root);
		siz[root] += siz[v];
	}
}

int centroid;
void GetCentroid(int root, int fa) {
	int maxx = sum - siz[root];
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v;
		if (v == fa || del[v]) continue;
		GetCentroid(v, root);
		maxx = max(maxx, siz[v]);
	}
	if (maxx <= sum / 2) {
		centroid = root;
	}
}

int vis[MAXK][2]; // vis[i][0] : can reach, vis[i][1] : len
int k, ans = 0x7fffffff;
void Count(int root, int fa, int c, int len) {
	if (c > k) return ;
	if (c == k) ans = min(ans, len);
	if (vis[k - c][0]) {
		ans = min(ans, len + vis[k - c][1]);
	}
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		if (v == fa || del[v]) continue;
		Count(v, root, c + w, len + 1);
	}
}

int que[MAXN], qcnt;
void Update(int root, int fa, int c, int len) {
	if (c > k) return ;
	vis[c][0] = 1;
	vis[c][1] = !vis[c][1] ? len : min(vis[c][1], len);
	que[++qcnt] = c;
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		if (v == fa || del[v]) continue;
		Update(v, root, c + w, len + 1);
	}
}

void Solve(int root) {
	sum = 0;
	CalcSumAndSiz(root, 0);
	GetCentroid(root, 0);
	root = centroid;
	del[root] = 1;
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v, w = edge[i].w;
		if (del[v]) continue;
		Count(v, root, w, 1);
		Update(v, root, w, 1);
	}
	for (int i = 1; i <= qcnt; ++i) {
		vis[que[i]][0] = 0;
		vis[que[i]][1] = 0;
	}
	qcnt = 0;
	for (int i = head[root]; i; i = edge[i].next) {
		int v = edge[i].v;
		if (del[v]) continue;
		Solve(v);
	}
}

int n;

int main() {
	freopen("ioi2011-race.in", "r", stdin);
	freopen("ioi2011-race.out", "w", stdout);
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n - 1; ++i) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		u++, v++;
		AddEdge(u, v, w);
		AddEdge(v, u, w);
	}
	
	Solve(1);
	
	printf("%d", ans == 0x7fffffff ? -1 : ans);
	return 0;
}