【洛谷P4149】【IOI2011】——Race(点分治)

感觉完全厌倦了文化课
什么都不想干

算了还是回归正题吧

传送门

一看就知道是淀粉质 点分治

我们只需要在每次处理的时候处理三个东西
$dis[u]$表示点$u$到当前子树重心的距离
$dep[u]$表示点$u$到当前子树重心经过的边数（就是深度）
$tmp[i]$表示到当前子树重心距离为$i$所需要的最少边数
这些都可以直接每次处理出来
然后一边搜索一边更新答案就是了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register 
inline int read(){
	char ch=getchar();int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res*f;
}
const int N=200005;
const ll inf=1000000000;
#define min(a,b) ((a)<(b))?(a):(b)
#define max(a,b) ((a)>(b))?(a):(b)
int adj[N],n,k,ans,nxt[N<<1],root,to[N<<1],val[N<<1],cnt,tmp[1000005],dep[N],siz[N],maxn,son[N];
ll dis[N];
bool vis[N];
inline void addedge(int u,int v,int w){
	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
inline void getroot(int u,int fa){
    siz[u]=1,son[u]=0;
    for(re int e=adj[u],v;e;e=nxt[e]){
    	v=to[e];
    	if(v!=fa&&!vis[v]){
    	    getroot(v,u);
    	    siz[u]+=siz[v];
    	    son[u]=max(son[u],siz[v]);
    	}
    }
    son[u]=max(son[u],maxn-siz[u]);
    if (son[u]<son[root]) root=u;
}
inline void calc(int u,int fa){
	if(dis[u]<=k)ans=min(ans,tmp[k-dis[u]]+dep[u]);
	for(re int e=adj[u],v;e;e=nxt[e]){
		v=to[e];
		if(vis[v]||v==fa)continue;
		dis[v]=dis[u]+val[e],dep[v]=dep[u]+1;
		calc(v,u);
	}
}
inline void getans(int u,int fa){
	if(dis[u]<=k)tmp[dis[u]]=min(tmp[dis[u]],dep[u]);
	for(re int e=adj[u],v;e;e=nxt[e]){
		v=to[e];
		if(v==fa||vis[v])continue;
		getans(v,u);
	}
}
inline void getback(int u,int fa){
	if(dis[u]<=k)tmp[dis[u]]=inf;
	for(re int e=adj[u],v;e;e=nxt[e]){
		v=to[e];
		if(v==fa||vis[v])continue;
		getback(v,u);
	}
}
inline void solve(int u){
	vis[u]=true,tmp[0]=0;
	for(re int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(vis[v])continue;
		dep[v]=1,dis[v]=val[e];
		getroot(v,root=0);
		calc(v,0),getans(v,0);
	}
	for(re int e=adj[u];e;e=nxt[e])if(!vis[to[e]])getback(to[e],0);
	for(re int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(vis[v])continue;
		maxn=siz[v],getroot(v,root=0);
		solve(root);
	}
}
signed main(){
	son[0]=maxn=n=read(),k=read();ans=inf;
	for(re int i=0;i<=1000000;++i)tmp[i]=inf;
	int u,v,w;
	for(re int i=1;i<n;++i){
		u=read()+1,v=read()+1,w=read();
		addedge(u,v,w),addedge(v,u,w);
	}
	getroot(1,root=0);
	//cout<<root;
	solve(root);
	if(ans>=inf)cout<<-1;
	else cout<<ans;
}