题意：
洛谷的地址
给一棵树，每条边有权。求一条简单路径，权值和等于 K ，且边的数量最小。
思路：
这题bzoj下线了，就去洛谷上A的
其实是一个比较简单的点分治
但是这题和之前的点分治不太一样（这题），这里的要求和之前不一样，我们不能算完重心的情况再去算子树的情况了
我们换一个思路，我们先遍历一颗以重心的儿子为根的子树，然后和一个之前的num（num[i]表示，到重心距离为i时最少经过几个边）数组来更新答案，更新完后，再把这棵子树的东西放进num数组，这样就能很好地排除非法情况（就是两点的简单路径不经过重心）
之后就和正常点分治一样了
错误及反思：
其实上面的都很好想，也不难写。然后就开始十分诡异的RE,TLE了，我在统计每颗子树的时候，把fa写成-1是tle，写成now却是re，然后就找了一下午bug，重写了一次，把vector改成手动模拟，也还是过不了
后来看了看别人的写法，把num数组的清空方式改了一下（之前是每次都memset，后来改成再重新跑一次，把经过的地方都修改回去），就AC了，甚至fa写错了都能AC。。。
可是我们计算一下复杂度，每次都memset的复杂度是 O(logn?(n+memset(1e6的数组))) ,这样是tle或re，改了以后是 O(logn?(n+n)) ，可是memset很快的啊，因为这个tle实在是搞不懂了。。。re就更神秘了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define fi first
#define se second
using namespace std;
const int N = 200100;
struct EDGE{int to,next,val;
}e[N*2];
int first[N],n,tot=0,si[N],maxn[N],num[1000010],k,ans=1e9,v[N][2],en;
bool did[N];void addedge(int x,int y,int z){e[tot].to=y;e[tot].val=z;e[tot].next=first[x];first[x]=tot++;e[tot].to=x;e[tot].val=z;e[tot].next=first[y];first[y]=tot++;
}
void dfs_size(int now,int fa){si[now]=1;maxn[now]=0;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to]){dfs_size(e[i].to,now);si[now]+=si[e[i].to];maxn[now]=max(maxn[now],si[e[i].to]);}
}
void dfs_root(int now,int fa,int& root,int& nu,int t){int MA=max(maxn[now],si[t]-si[now]);if(MA<nu){nu=MA;root=now;}for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to])dfs_root(e[i].to,now,root,nu,t);
}
void dfs2(int now,int fa,int tlen,int dep){if(tlen>k) return ;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa&&!did[e[i].to])dfs2(e[i].to,now,tlen+e[i].val,dep+1);v[en][0]=tlen;v[en++][1]=dep;
}void solve(int now){int root,nu=1e9;dfs_size(now,-1);dfs_root(now,-1,root,nu,now);num[0]=0;did[root]=true;for(int i=first[root];i!=-1;i=e[i].next){if(!did[e[i].to]){en=0;dfs2(e[i].to,root,e[i].val,1);//很神秘的地方，把fa写成-1是tle，写成now却是re，换了num的写法后却都能ac。。。for(int j=0;j<en;j++)ans=min(ans,v[j][1]+num[k-v[j][0]]);for(int j=0;j<en;j++)num[v[j][0]]=min(num[v[j][0]],v[j][1]);}}for(int i=first[root];i!=-1;i=e[i].next){if(!did[e[i].to]){en=0;dfs2(e[i].to,root,e[i].val,1);for(int j=0;j<en;j++)num[v[j][0]]=1e9;}}for(int i=first[root];i!=-1;i=e[i].next)if(!did[e[i].to])solve(e[i].to);
}
int main(){memset(first,-1,sizeof(first));scanf("%d%d",&n,&k);for(int i=1;i<=k;i++) num[i]=1e9;//这里只写一次，而不是每次都memsetfor(int i=0,u,v,w;i<n-1;i++){scanf("%d%d%d",&u,&v,&w);addedge(u+1,v+1,w);}solve(1);if(ans==1e9) printf("-1\n");else printf("%d\n",ans);
}