题面：（复制别人的。。。）
Description
给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.
Input
第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)
Output
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
Sample Input
4 3
0 1 1
1 2 2
1 3 4
0 1 1
1 2 2
1 3 4
Sample Output
2
这道题好像是权限题。。bzoj上看不到这道题更别说交了。。。
写了半天结果交不了，样例过了就当过了吧。。QAQ
思路：
多建一个cnt数组表示权值为i的最小边长，得到每个点到根节点的边长和权值和然后逐个更新就好了。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e5 + ;
int n,k,cnt1,root,f[M],head[M],siz[M],cnt[M],dis[M],vis[M],sum,ans; struct node{
int to,next,w;
}e[M]; void add(int u,int v,int w){
e[++cnt1].to=v;e[cnt1].next=head[u];e[cnt1].w=w;head[u]=cnt1;
} void get_root(int u,int fa){
f[u] = ; siz[u] = ;
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v == fa||vis[v]) continue;
get_root(v,u);
siz[u] += siz[v];
f[u] = max(f[u],siz[v]);
}
f[u] = max(sum-siz[u],f[u]);
if(f[u] < f[root]) root = u;
} void get_dis(int u,int fa,int dep){
if(dis[u] >= &&dis[u] <= k) ans = min(ans,dep + cnt[k-dis[u]]);
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v==fa||vis[v]) continue;
dis[v] = dis[u] + e[i].w;
get_dis(v,u,dep+);
}
} void cal(int u,int fa,int dep,int flag){
if(dis[u] >= &&dis[u] <= k) {
if(flag) cnt[dis[u]] = min(dep,cnt[dis[u]]);
else cnt[dis[u]] = n;
}
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v==fa||vis[v]) continue;
cal(v,u,dep+,flag);
}
} void solve(int u){
vis[u] = ; cnt[] = ;
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(vis[v]) continue;
dis[v] = e[i].w;
get_dis(v,,);
cal(v,,,);
}
for(int i = head[u];i;i=e[i].next){ //初始化
int v = e[i].to;
if(vis[v]) continue;
cal(v,,,);
}
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(vis[v]) continue;
root = ;
sum = siz[v];
get_root(v,);
solve(v);
}
} int main()
{
int a,b,c;
scanf("%d%d",&n,&k);
ans = n;cnt1=;
for(int i = ;i < n;i ++){
scanf("%d%d%d",&a,&b,&c);
a++;b++;
add(a,b,c); add(b,a,c);
}
for(int i = ;i <= k;i ++) cnt[i] = n;
root = ;f[] = n; sum = n;get_root(,);
solve(root);
printf("%d\n",(ans==n)?-:ans);
}