[文章目录]
Description
给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 10^6
点分治，桶统计过每个点的块内连接不同儿子的链中对应每个权值的最少的边的数量。时间复杂度O(nlogn)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000
const int inf=0x3f3f3f3f;
int n,k,ans=inf;
int head[N],to[N<<1],nxt[N<<1],f[N<<1],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
int msi[N],siz[N],root,nn;
int t[1001000],dis[N],num[N],tot;
bool vis[N];
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
siz[x]+=siz[to[i]],getroot(to[i],x),msi[x]=max(msi[x],siz[to[i]]);
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre,int Num,int Dis)
{
dis[++tot]=Dis; num[tot]=Num; siz[x]=1;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
Dfs(to[i],x,Num+1,Dis+f[i]),siz[x]+=siz[to[i]];
}
void solve(int x)
{
int i,j,last;
tot=1; dis[tot]=0; num[tot]=0;
t[0]=0; vis[x]=1;
for(i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
last=tot;
Dfs(to[i],x,1,f[i]);
for(j=last+1;j<=tot;++j) if(dis[j]<=k)
ans=min(ans,t[k-dis[j]]+num[j]);
for(j=last+1;j<=tot;++j) if(dis[j]<=k)
t[dis[j]]=min(t[dis[j]],num[j]);
}
for(i=1;i<=tot;++i) if(dis[i]<=k) t[dis[i]]=inf;
for(i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
nn=siz[to[i]];
root=0;
getroot(to[i],x);
solve(root);
}
}
int main()
{
scanf("%d%d",&n,&k);
int i,x,y,z;
for(i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
x++,y++; add(x,y,z); add(y,x,z);
}
memset(t,0x3f,sizeof(int)*(k+10));
nn=n; msi[0]=inf; getroot(1,0); solve(root);
if(ans==inf) puts("-1");
else printf("%d\n",ans);
return 0;
}