【BZOJ2599】【IOI2011】Race

  裸的点分治，每次DFS暴力更新就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200010,maxk=1000010,inf=~0U>>1;

int head[maxn],next[maxn<<1],E[maxn<<1],D[maxn<<1],Ecnt;
int sons[maxn];
int f[maxk],po[maxk];
int vis[maxk];
int root,rootsize;
int n,k,ans;

void Add_Edge(int x,int y,int dis) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=dis;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=dis;}

int Q[maxn],Qf[maxn],Qtop;

void Solve_DFS(int x,int dis,int dep,int fa)
{
	if (dis>k) return;
	Q[Qtop]=dis;Qf[Qtop]=dep;Qtop++;
	for (int i=head[x];i;i=next[i]) if (!vis[E[i]] && E[i]!=fa)
		Solve_DFS(E[i],dis+D[i],dep+1,x);
}

void Solve(int x)
{
	po[0]=x;
	for (int i=head[x];i;i=next[i]) if (!vis[E[i]])
	{
		Qtop=0;
		Solve_DFS(E[i],D[i],1,x);
		for (int j=0;j<Qtop;j++) if (po[k-Q[j]]==x && Qf[j]+f[k-Q[j]]<ans) ans=Qf[j]+f[k-Q[j]];
		for (int j=0;j<Qtop;j++)
		{
			if (po[Q[j]]!=x) po[Q[j]]=x,f[Q[j]]=Qf[j];
			else if (Qf[j]<f[Q[j]]) f[Q[j]]=Qf[j];
		}
	}
}

int FindRoot(int x,int fa,int N)
{
	int tsize=0;
	sons[x]=0;
	for (int i=head[x];i;i=next[i]) if (E[i]!=fa && !vis[E[i]])
	{
		int tsons=FindRoot(E[i],x,N);
		sons[x]+=tsons;
		if (tsons>tsize) tsize=tsons;
	}
	if (N-sons[x]-1>tsize) tsize=N-sons[x]-1;
	if (rootsize>tsize) root=x,rootsize=tsize;
	return sons[x]+1;
}

void Divide_DFS(int x,int N)
{
	if (N==1) return;
	root=x;rootsize=n;
	FindRoot(x,0,N);
	x=root;
	Solve(x);
	vis[x]=1;
	for (int i=head[x];i;i=next[i]) if (!vis[E[i]])
		if (sons[E[i]]<sons[x]) Divide_DFS(E[i],sons[E[i]]);else Divide_DFS(E[i],N-sons[x]);
}

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

int main()
{
	read(n),read(k);
	for (int i=0,x,y,c;i<n-1;i++) read(x),read(y),read(c),x++,y++,Add_Edge(x,y,c);
	ans=inf;
	Divide_DFS(1,n);
	if (ans==inf) puts("-1");else printf("%d\n",ans);
	return 0;
}