题目描述
给一棵树，每条边有权。求一条简单路径，权值和等于 KK，且边的数量最小。

输入格式
第一行包含两个整数 n, Kn,K。

接下来 n - 1n−1 行，每行包含三个整数，表示一条无向边的两端和权值。

注意点的编号从 00 开始。

输出格式
输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 -1−1。

输入输出样例
输入 #1复制
4 3
0 1 1
1 2 2
1 3 4
输出 #1复制
2
说明/提示
保证 n \leqslant 2 \times 10^5,n⩽2×10
5
, K \leqslant 10^6K⩽10
6
。

是不是和点分治的模板题很相似？

其实就是点分治，我们维护一下当前到根距离的最小边数，而不是单单只维护是否出现。

然后就可以AC了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,k,rt,sz[N],vis[N],sum,mx,res=inf,st[N*5],now1[N],now2[N],q[N*5];
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
void get(int x,int fa){
	sz[x]=1; int t=0;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]]||to[i]==fa)	continue;
		get(to[i],x); sz[x]+=sz[to[i]]; t=max(t,sz[to[i]]);
	}
	t=max(t,sum-sz[x]); if(t<mx) mx=t,rt=x;
}
void getdis(int x,int fa,int d1,int d2){
	if(d1>k)	return ;
	now1[++now1[0]]=d1; now2[now1[0]]=d2;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]]||to[i]==fa)	continue;	getdis(to[i],x,d1+w[i],d2+1);
	}
}
void solve(int x){
	q[0]=0;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		now1[0]=0;	getdis(to[i],x,w[i],1);
		for(int j=1;j<=now1[0];j++)	res=min(res,st[k-now1[j]]+now2[j]);
		for(int j=1;j<=now1[0];j++){
			st[now1[j]]=min(st[now1[j]],now2[j]);	q[++q[0]]=now1[j];
		}
	}
	for(int i=1;i<=q[0];i++)	st[q[i]]=inf;
}
void divide(int x){
	vis[x]=1;	st[0]=0;	solve(x);
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		sum=sz[to[i]]; mx=inf; rt=0; get(to[i],0); get(rt,0);
		divide(rt);
	}
}
signed main(){
	cin>>n>>k;	memset(st,0x3f,sizeof st);
	for(int i=1,a,b,c;i<n;i++)	scanf("%d %d %d",&a,&b,&c),a++,b++,add(a,b,c),add(b,a,c);
	mx=sum=n; get(1,0); get(rt,0); divide(rt);
	printf("%d\n",res>=n?-1:res);
	return 0;
}