比赛 |
20200109 |
评测结果 |
AAAAAAAAAA |
题目名称 |
树网的核 |
最终得分 |
100 |
用户昵称 |
00000 |
运行时间 |
0.005 s |
代码语言 |
C++ |
内存使用 |
4.42 MiB |
提交时间 |
2019-12-25 21:57:44 |
显示代码纯文本
#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 ;
}