#include<bits/stdc++.h>
using namespace std;
int read() {
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
void write(int x) {
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
const int N=3e5+10,K=1e6+10;
int n,k;
int h[N],ver[N<<1],nxt[N<<1],edge[N<<1],tot;
void addEdge(int x,int y,int z) {
	ver[++tot]=y; nxt[tot]=h[x]; edge[tot]=z; h[x]=tot;
	ver[++tot]=x; nxt[tot]=h[y]; edge[tot]=z; h[y]=tot;
}
int al,son[N],sz[N],root;
bool vis[N];
void getroot(int x,int fa) {
	sz[x]=1; son[x]=0;
//	cout<<x<<" "<<fa<<endl;
	for(int i=h[x];i;i=nxt[i]) {
		int y=ver[i];
		if(y==fa || vis[y]) continue;
		getroot(y,x);
		sz[x]+=sz[y];
		son[x]=max(son[x],sz[y]);
	}
	son[x]=max(son[x],al-sz[x]);
	if(son[root]>son[x]) root=x;
}
int mini[K],dl,dis1[N],dis2[N],ans;
void getdis(int x,int fa,int d1,int d2) {
	if(d1>k) return ;
	dis1[++dl]=d1; dis2[dl]=d2;
	for(int i=h[x];i;i=nxt[i]) {
		int y=ver[i],z=edge[i];
		if(y==fa || vis[y]) continue;
		getdis(y,x,d1+z,d2+1);
	}
}
void getans(int x) {
	mini[0]=0; dl=0;
	for(int i=h[x];i;i=nxt[i]) {
		int y=ver[i],z=edge[i];
		if(vis[y]) continue;
		int pdl=dl;
		getdis(y,x,z,1);
		for(int j=pdl+1;j<=dl;j++) ans=min(ans,mini[k-dis1[j]]+dis2[j]);
		for(int j=pdl+1;j<=dl;j++) mini[dis1[j]]=min(mini[dis1[j]],dis2[j]);
	}
	for(int i=1;i<=dl;i++) mini[dis1[i]]=1e9;
}
void solve(int x) {
	vis[x]=true;
//	cout<<x<<endl;
	getans(x);
	for(int i=h[x];i;i=nxt[i]) {
		int y=ver[i];
		if(vis[y]) continue;
		al=sz[y]; root=0;
		getroot(y,x);
		solve(y);
	}
}
int main() {
	n=read(); k=read();
	for(int i=1;i<n;i++) {
		int x=read(),y=read(),z=read();
		addEdge(x+1,y+1,z);
	}
	son[0]=(al=n)+1; memset(mini,0x3f,sizeof(mini)); ans=1e9;
//	cout<<son[0]<<" "<<al<<endl;
	getroot(1,0);
	solve(root);
	printf("%d\n",ans>=n?-1:ans);
    return 0;
}

参考的是tj第一篇代码

#5 TLE

看了眼数据发现#5时 是一条链

然后自己调了一下发现是getroot写超时了

但又不知道哪里有问题 求助qaq