一道很水的点分治模板。
分两种路径,进行分治。
在更新每一颗子树之前,更新答案就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int n,bz,last[N],len,c[N],mx[N],root,sum;
struct edge{int y,d,next;}a[N<<1];
inline void ins(int x,int y,int d){a[++len]=(edge){y,d,last[x]};last[x]=len;}
bool v[N];
void findroot(int x,int f)
{
c[x]=1;mx[x]=-1;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(y==f||v[y])continue;
findroot(y,x);c[x]+=c[y];mx[x]=max(mx[x],c[y]);
}
mx[x]=max(mx[x],sum-mx[x]);
if(mx[x]<mx[root])root=x;
}
int g[N*5],ans;//g[i]表示路径到现在的根的距离为i的最少边数。
void updans(int x,int f,int dis,int cnt)
{
if(dis>bz)return ;
ans=min(ans,g[bz-dis]+cnt);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(y==f||v[y])continue;
updans(y,x,dis+a[k].d,cnt+1);
}
}
void update(int x,int f,int dis,int cnt)
{
if(dis>bz)return ;
g[dis]=min(g[dis],cnt);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(y==f||v[y])continue;
update(y,x,dis+a[k].d,cnt+1);
}
}
void clear(int x,int f,int dis)
{
if(dis>bz)return ;
g[dis]=inf;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(y==f||v[y])continue;
clear(y,x,dis+a[k].d);
}
}
void dfs(int x)
{
g[0]=0;v[x]=1;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(v[y])continue;
updans(y,x,a[k].d,1);//更新答案
update(y,x,a[k].d,1);//更新状态
}
clear(x,0,0);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;if(v[y])continue;
sum=c[y];root=0;findroot(y,0);
dfs(root);
}
}
int main()
{
//freopen("a.in","r",stdin);
qr(n),qr(bz);
for(int i=1,x,y,d;i<n;i++)qr(x),qr(y),qr(d),++x,++y,ins(x,y,d),ins(y,x,d);
mx[0]=inf;memset(g,0x3f,sizeof(g));
sum=n;root=0;findroot(1,0);
ans=inf;dfs(root);
if(ans!=inf)qw(ans),puts("");
else puts("-1");
return 0;
}
最后一次更新于2019-10-14
0 条评论