题目描述
给一棵树，每条边有权。求一条简单路径，权值和等于 KKK，且边的数量最小。
输入格式
第一行包含两个整数 n,K。
接下来 n−1 行，每行包含三个整数，表示一条无向边的两端和权值。
注意点的编号从 0 开始。
输出格式
输出一个整数，表示最小边数量。
如果不存在这样的路径，输出 −1。
板子题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
const int N=2e5+5;
int nxt[N<<1],head[N],go[N<<1],w[N<<1],tot;
inline void Add(int u,int v,int o){
nxt[++tot]=head[u];head[u]=tot;go[tot]=v;w[tot]=o;
nxt[++tot]=head[v];head[v]=tot;go[tot]=u;w[tot]=o;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,K,sum,root,ans;
int t[1000005],son[N],f[N],dis[N],d[N];
bool vis[N];
inline void getroot(int x,int fa){
son[x]=1; f[x]=0;
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(v==fa||vis[v])continue;
getroot(v,x);
son[x]+=son[v];
f[x]=max(f[x],son[v]);
}
f[x]=max(f[x],sum-son[x]);
if(f[x]<f[root])root=x;
}
inline void cal(int x,int fa){
if(dis[x]<=K)ans=min(ans,d[x]+t[K-dis[x]]);
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(v==fa||vis[v])continue;
d[v]=d[x]+1;
dis[v]=dis[x]+w[i];
cal(v,x);
}
}
inline void add(int x,int fa,bool flag){
if(dis[x]<=K){
if(flag)t[dis[x]]=min(t[dis[x]],d[x]);
else t[dis[x]]=inf;
}
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(v==fa||vis[v])continue;
add(v,x,flag);
}
}
inline void work(int x){
vis[x]=1; t[0]=0;
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(vis[v])continue;
d[v]=1; dis[v]=w[i];
cal(v,0);
add(v,0,1);
}
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(vis[v])continue;
add(v,0,0);
}
for(int i=head[x];i;i=nxt[i]){
int v=go[i];
if(vis[v])continue;
root=0; sum=son[v];
getroot(v,0);
work(root);
}
}
signed main(){
n=read(); K=read();
for(int i=1;i<=K;i++)t[i]=n;
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
u++,v++;
Add(u,v,w);
}
ans=sum=f[0]=n;
getroot(1,0);
work(root);
if(ans!=n)printf("%d
",ans);
else puts("-1");
}