题意：
给一棵树，每条边有权。求一条简单路径，权值和等于K，且边的数量最小。
分析：
对于这道题，和计算长度恰好为k的路径数量差不多，只不过那个所谓的桶里不装数量，装达到这个长度的最小的边数。
（感觉把这个桶应用好，能解决点分治的不少题目）
当然呢，为了进一步节约时间，我们不必每次都把桶memset一次，只需要把用过的位置都记录下来，用完后还原即可。
这里有两种实现方法，一个较长一个较短，一个稍快一个稍慢。
其实这个题还有一种做法，就是树上启发式合并（不过我并没有去写）一道好题目本来就是很多种思路的火种，建议大家用不同的方法实现这道题。
代码：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #include<cmath>
6 #define ll long long
7 using namespace std;
8 const int N=200005;int rt,sum;
9 struct node{int y,z,nxt;}edge[N*2];
10 int n,k,head[N],cn=0,siz[N],son[N];
11 void add(int x,int y,int z){
12 edge[++cn]=(node){y,z,head[x]};head[x]=cn;
13 edge[++cn]=(node){x,z,head[y]};head[y]=cn;
14 } bool vis[N];
15 void getrt(int x,int fa){
16 siz[x]=1;son[x]=0;
17 for(int i=head[x],y;~i;i=edge[i].nxt){
18 if((y=edge[i].y)==fa||vis[y])continue;
19 getrt(y,x);siz[x]+=siz[y];
20 if(son[x]<siz[y]) son[x]=siz[y];
21 } son[x]=max(son[x],sum-siz[x]);
22 if(son[x]<son[rt]) rt=x;
23 } int tmp[N*10],ans=1e9;
24 void dfs(int x,int fa,int d,int cnt){
25 if(d>k) return ;
26 ans=min(ans,tmp[k-d]+cnt);
27 for(int i=head[x],y;~i;i=edge[i].nxt){
28 y=edge[i].y;if(y==fa||vis[y])continue;
29 dfs(y,x,d+edge[i].z,cnt+1);
30 } return ;
31 }
32 void update(int x,int fa,int d,int cnt){
33 if(d>k) return ;
34 tmp[d]=min(tmp[d],cnt);
35 for(int i=head[x],y;~i;i=edge[i].nxt){
36 y=edge[i].y;if(y==fa||vis[y])continue;
37 update(y,x,d+edge[i].z,cnt+1);
38 } return ;
39 }
40 void clear(int x,int fa,int d){
41 if(d>k) return ;tmp[d]=1e9;
42 for(int i=head[x],y;~i;i=edge[i].nxt){
43 y=edge[i].y;if(y==fa||vis[y])continue;
44 clear(y,x,d+edge[i].z);
45 }return ;
46 }
47 void solve(int x,int sz){
48 tmp[0]=0;vis[x]=1;
49 for(int i=head[x],y;~i;i=edge[i].nxt){
50 if(vis[y=edge[i].y]) continue;
51 dfs(y,x,edge[i].z,1);
52 update(y,x,edge[i].z,1);
53 } clear(x,0,0);
54 for(int i=head[x],y;~i;i=edge[i].nxt){
55 if(vis[y=edge[i].y]) continue;
56 sum=(siz[y]>siz[x]?sz-siz[x]:siz[y]);
57 rt=0;son[0]=sum;getrt(y,0);
58 solve(rt,sum);
59 } return ;
60 }
61 int main(){
62 memset(head,-1,sizeof(head));
63 scanf("%d%d",&n,&k);int t1,t2,t3;
64 for(int i=1;i<n;i++){
65 scanf("%d%d%d",&t1,&t2,&t3);
66 add(t1+1,t2+1,t3);
67 } for(int i=0;i<=k;i++) tmp[i]=1e9;
68 sum=n;rt=0;son[0]=n;
69 getrt(1,0);solve(rt,n);
70 if(ans!=1e9) printf("%d\n",ans);
71 else puts("-1");return 0;
72 }
点分治
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int N=2000005,M=1000005;
5 struct link{int l,d;}q[N];
6 int h[N],n,m,k,mx[N],dis[N];
7 ll t[M],ans=0;int sm,tmp[N];
8 struct node{int y,z,nxt;}e[N*2];
9 int d[N],rt,vis[N],siz[N],c=1,cnt=0;
10 void add(int x,int y,int z){
11 e[++c]=(node){y,z,h[x]};h[x]=c;
12 e[++c]=(node){x,z,h[y]};h[y]=c;
13 } void getrt(int x,int fa){
14 siz[x]=1;mx[x]=0;
15 for(int i=h[x],y;i;i=e[i].nxt)
16 if((y=e[i].y)!=fa&&!vis[y])
17 getrt(y,x),siz[x]+=siz[y],
18 mx[x]=max(mx[x],siz[y]);
19 mx[x]=max(mx[x],sm-siz[x]);
20 if(mx[x]<mx[rt]) rt=x;return ;
21 } void dfs(int x,int fa){
22 q[++cnt]=(link){d[x],dis[x]};
23 for(int i=h[x],y;i;i=e[i].nxt)
24 if((y=e[i].y)!=fa&&!vis[y])
25 d[y]=d[x]+e[i].z,dis[y]=dis[x]+1,
26 dfs(y,x);return ;
27 } void calc(int x){ tmp[0]=0;
28 for(int i=h[x],y;i;i=e[i].nxt)
29 if(!vis[y=e[i].y]){
30 cnt=0;d[y]=e[i].z;dis[y]=1;dfs(y,x);
31 for(int j=cnt;j;j--)
32 if(q[j].l<=k) ans=
33 min(t[k-q[j].l]+q[j].d,ans);
34 for(int j=cnt;j;j--)
35 if(q[j].l<=k) t[q[j].l]=
36 min(t[q[j].l],q[j].d*1ll),
37 tmp[++tmp[0]]=q[j].l;
38 } for(int i=tmp[0];i;i--) t[tmp[i]]=2e9;
39 } void solve(int x){
40 vis[x]=1;t[0]=0;calc(x);
41 for(int i=h[x],y;i;i=e[i].nxt)
42 if(!vis[y=e[i].y]){
43 sm=siz[y];mx[rt=0]=N;
44 getrt(y,0);solve(rt);
45 } return ;
46 } int main(){
47 scanf("%d%d",&n,&k);ans=2e9;
48 memset(t,0x3f,sizeof(t));
49 for(int i=1,x,y,z;i<n;i++)
50 scanf("%d%d%d",&x,&y,&z),
51 add(x+1,y+1,z);mx[rt]=sm=n;
52 getrt(1,0);solve(rt);
53 if(ans>=1e9) puts("-1");else
54 printf("%lld\n",ans);return 0;
55 }
点分治（较短）