该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题意】（数据加强）
设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 $T$ 为树网（`treenetwork`），其中 $V$，$E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。

路径：树网中任何两结点 $a$，$b$ 都存在唯一的一条简单路径，用 $d(a, b)$ 表示以 $a, b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称 $d(a, b)$ 为 $a, b$ 两结点间的距离。

$D(v, P)=\min\{d(v, u)\}$, $u$ 为路径 $P$ 上的结点。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 $\mathrm{ECC}(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离，即$\mathrm{ECC}(F)=\max\{D(v, F),v \in V\}$

任务：对于给定的树网 $T=(V, E, W)$ 和非负整数 $s$，求一个路径 $F$，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$（可以等于 $s$），使偏心距 $\mathrm{ECC}(F)$ 最小。我们称这个路径为树网 $T=(V, E, W)$ 的核（`Core`）。必要时，$F$ 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中，$A-B$ 与 $A-C$ 是两条直径，长度均为 $20$。点 $W$ 是树网的中心，$EF$ 边的长度为 $5$。如果指定 $s=11$，则树网的核为路径`DEFG`（也可以取为路径`DEF`），偏心距为 $8$。如果指定 $s=0$（或 $s=1$、$s=2$），则树网的核为结点 $F$，偏心距为 $12$。


【输入格式】
共 $n$ 行。
第 $1$ 行，两个正整数 $n$ 和 $s$，中间用一个空格隔开。其中 $n$ 为树网结点的个数，$s$ 为树网的核的长度的上界。设结点编号以此为 $1,2\dots,n$。
从第 $2$ 行到第 $n$ 行，每行给出 $3$ 个用空格隔开的正整数 $u, v, w$，依次表示每一条边的两个端点编号和长度。例如，`2 4 7` 表示连接结点 $2$ 与 $4$ 的边的长度为 $7$。

【输出格式】
一个非负整数，为指定意义下的最小偏心距。

【样例输入 #1】
5 2
1 2 5
2 3 2
2 4 4
2 5 3

【样例输出 #1】
5

【样例输入 #2】
8 6
1 3 2
2 3 2 
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

【样例输出 #2】
5

【提示】
- 对于 $100\%$ 的数据，保证 $2\le n \le 500000$，$0\le s < 2^{31}$，$1 \leq u, v \leq n$，$0 \leq 树的直径长度 < 2^{31}$。

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<pair<int,int>>G[N];
int d[N], dis, h[N], fa, f[N]; bool v[N]; 
void dfs1(int x)
{
	v[x]=1;
	for(auto i:G[x])
	{
		int y=i.first,c=i.second; if(v[y]==1) continue;
		d[y]=d[x]+c; f[y]=x;
		if(dis<d[y]) dis=d[y], fa=y;
		dfs1(y);
	}
}
void dfs2(int x)
{
	v[x]=1;
	for(auto i:G[x])
	{
		int y=i.first,c=i.second; if(v[y]==1) continue;
		dfs2(y);
		h[x]=max(h[x], h[y]+c); 
	}
}
int main()
{
	int n,S; scanf("%d%d", &n, &S);
	for(int i=1,x,y,c; i<n; i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		G[x].push_back({y,c}); G[y].push_back({x,c});
	}
	int l, r; 
	memset(v, 0, sizeof(v)); 
	d[1]=0;f[1]=0; dis=0; dfs1(1); l=fa;
	memset(v, 0, sizeof(v)); 
	d[l]=0;f[l]=0; dis=0; dfs1(l); r=fa;
memset(v&#44; 0&#44; sizeof(v));
memset(h&#44; 0&#44; sizeof(h));
for(int i=r; i; i=f[i]) v[i]=1;
int maxh=0; 
for(int i=r; i; i=f[i]) dfs2(i)&#44; maxh=max(maxh&#44; h[i]);

int ans=(1LL&lt;&lt;31)-1;
for(int i=r&#44; j=r; i; i=f[i])
{
	while(d[j]-d[i]&gt;S) j=f[j];
	ans=min(ans&#44; max({maxh&#44; d[i]-d[l]&#44; d[r]-d[j]}));
}
printf("%d\n"&#44; ans);
return 0;

}

</p>