0、题意：给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.
1、分析：水题一道，一波树分治就好
我们可以发现这个题的K是比较小的，才100w，那么我们可以树分治一下，在遍历每一棵子树的时候我们知道要统计两个不同子树之间的权值，如果我们全遍历然后再getans，我们就会发现某个子树自己会和自己进行统计了一下，这样不太好，所有我们每遍历一个子树我们就把这个子树中从x所有长度为k的路径记录上v[k]=边数，记住要取min，然后询问我们还是遍历子树，我们查询v[K - k]然后统计答案。。这样我们就能轻松的查询了，最后别忘记把所有v数组清空，记住不要memset，会TLE，我们还是再次的遍历一下。。
然后我们就AC了
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define M 2000010
inline int read(){
char ch=getchar(); int x=0,f=1;
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
struct Edge{
int u,v,w,next;
} G[M];
int head[M],tot;
int mx[M],size[M],ok[M],mi,root;
int n,k,V[M],ans;
int vis[M];
inline void add(int u,int v,int w){
G[++tot]=(Edge){u,v,w,head[u]};
head[u]=tot;
}
inline void dfssize(int x,int fa){
size[x]=1;mx[x]=0;
for(int i=head[x];i!=-1;i=G[i].next) if(G[i].v!=fa&&!ok[G[i].v]){
dfssize(G[i].v,x);
size[x]+=size[G[i].v];
if(size[G[i].v]>mx[x]) mx[x]=size[G[i].v];
}
}
inline void getroot(int r,int x,int fa){
if(size[r]-size[x]>mx[x]) mx[x]=size[r]-size[x];
if(mx[x]<mi) mi=mx[x],root=x;
for(int i=head[x];i!=-1;i=G[i].next) if(G[i].v!=fa&&!ok[G[i].v]){
getroot(r,G[i].v,x);
}
}
inline void dfs_getans(int x,int fa,int edge,int val){
if(val>k)return;
if(val==k){
ans=min(ans,edge);
return;
}
int o=k-val;
if(V[o]!=0){
ans=min(ans,edge+V[o]);
}
for(int i=head[x];i!=-1;i=G[i].next) if(G[i].v!=fa&&!ok[G[i].v]){
dfs_getans(G[i].v,x,edge+1,val+G[i].w);
}
}
inline void dfs_insert(int x,int fa,int edge,int val){
if(val>=k)return;
if(!V[val]) V[val]=edge;
else V[val]=min(V[val],edge);
for(int i=head[x];i!=-1;i=G[i].next) if(G[i].v!=fa&&!ok[G[i].v]){
dfs_insert(G[i].v,x,edge+1,val+G[i].w);
}
}
inline void dfs_delete(int x,int fa,int edge,int val){
if(val>=k)return;
V[val]=0;
for(int i=head[x];i!=-1;i=G[i].next) if(G[i].v!=fa&&!ok[G[i].v]){
dfs_delete(G[i].v,x,edge+1,val+G[i].w);
}
}
inline void solve(int x){
mi=n; dfssize(x,0);
getroot(x,x,0);
ok[root]=1;
for(int i=head[root];i!=-1;i=G[i].next) if(!ok[G[i].v]){
dfs_getans(G[i].v,root,1,G[i].w);
dfs_insert(G[i].v,root,1,G[i].w);
}
for(int i=head[root];i!=-1;i=G[i].next) if(!ok[G[i].v]){
dfs_delete(G[i].v,root,1,G[i].w);
}
for(int i=head[root];i!=-1;i=G[i].next) if(!ok[G[i].v]){
solve(G[i].v);
}
}
int main(){
n=read(),k=read();
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
u++; v++;
add(u,v,w); add(v,u,w);
}
ans=214748364;
solve(1);
if(ans==214748364) puts("-1");
else printf("%d\n",ans);
return 0;
}