记录编号	156149	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]树网的核	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2015-04-02 21:45:21	内存使用	0.00 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 1999: [Noip2007]Core树网的核
* ALG    : 树的直径
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#include <cstring>
#include <algorithm>

//#define  maxn  500010LL
//#define  maxm  500010LL

#define  maxn  310LL
#define  maxm  310LL

struct FST { int to , next , len ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v , int w) { e[++tote].to = v ; e[tote].len = w ; e[tote].next = star[u] ; star[u] = tote ;  }

int n , limit , ans ;
int rootR , rootL ;
int q[maxn] , head , rear ;
int dis[maxn] = {0} ;
bool vis[maxn] = {0} ;
int fa[maxn] = {0} ;
int Dia[maxn] = {0} ;
int disL[maxn] , disR[maxn] , disM[maxn] ;

int main() {
int i , u , v , w , p , L , R ;
	#define READ
	#ifdef  READ
		freopen("core.in" ,"r",stdin ) ;
		freopen("core.out","w",stdout) ;
	#endif
	read(n) , read(limit) ;
	Rep (i,2,n) {
		read(u) , read(v) , read(w) ;
		AddEdge(u,v,w) ;
		AddEdge(v,u,w) ;
	}
	head = rear = 1 ;
	q[rear++] = rootR = 1 ;
	dis[1] = 0 ;
	vis[1] = true ;
	while (head < rear) {
		u = q[head++] ;
		for (p=star[u] ; p ; p=e[p].next)
			if (v=e[p].to , !vis[v]) {
				dis[v] = dis[u]+e[p].len ;
				q[rear++] = v ;
				vis[v] = true ;
				if (dis[v] > dis[rootR]) rootR = v ;
			}
	}
	head = rear = 1 ;
	q[rear++] = rootL = rootR ;
	dis[rootR] = 0 ;
	vis[rootR] = false ;
	while (head < rear) {
		u = q[head++] ;
		for (p=star[u] ; p ; p=e[p].next)
			if (v=e[p].to , vis[v]) {
				dis[v] = dis[u]+e[p].len ;
				fa[v] = u ;
				q[rear++] = v ;
				vis[v] = false ;
				if (dis[v] > dis[rootL]) rootL = v ;
			}
	}
	/* 两遍bfs找到直径端点 */

	u = rootL ;
	Dia[0] = 0 ;
	for ( ; u ; u=fa[u]) {
		Dia[++Dia[0]] = u , vis[u] = true ;
		disR[u] = dis[u] ;
		disL[u] = disR[Dia[1]]-disR[u] ;
	}
	/* Dia存储了树的直径,vis暂时对直径上的点进行了标记 */
	/* disL与disR记录了直径上每个端点距离最左端长度及距离最右端长度 */

	memset(dis , 0 , sizeof dis) ;
	Rep (i,1,Dia[0]) {
		head = rear = 1 ;
		q[rear++] = Dia[i] ;
		while (head < rear) {
			u = q[head++] ;
			for (p=star[u] ; p ; p=e[p].next)
				if (v=e[p].to , !vis[v]) {
					dis[v] = dis[u]+e[p].len ;
					q[rear++] = v ;
					vis[v] = true ;
					if (dis[v] > disM[Dia[i]]) disM[Dia[i]] = dis[v] ;
				}
		}
	}
	/* 求出直径上每个点除了直径上的点最远的点的距离 */

	head = rear = 1 ;
	L = 1 ;
	ans = std::max(disM[Dia[1]],disR[Dia[1]]) ;
	q[rear++] = Dia[1] ;
	Rep (R,2,Dia[0]) {
		while (head<rear && disR[q[head]]-disR[Dia[R]]>limit) head ++ ;
		while (head<rear && disM[Dia[R]]>disM[q[rear-1]]) rear -- ;
		q[rear++] = Dia[R] ;
		while (disR[Dia[L]]-disR[Dia[R]]>limit) L ++ ;
		ans = std::min(ans,std::max(disM[q[head]],std::max(disL[Dia[L]],disR[Dia[R]]))) ;
	}
	/* 记录当前选择的一段路径的左端点及右端点，并用单调队列维护所选路径的disM最大值，不断更新答案 */
	printf("%d\n", ans) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}