var yvu,lin:array[0..300]of boolean;
xu,poto,opo,long,ri:array[0..300]of longint;
g,dd:array[0..300,0..300]of longint;
ans,n,s,i,j,q,x,y,d,nl,i1,zhijing,st,ed,j1,sn:longint;
begin
readln(n,s);
zhijing:=0;
yvu[1]:=true;
xu[1]:=1;
for i:=2 to n do
begin
readln(x,y,d);
if yvu[y] then begin q:=x;x:=y;y:=q; end;
dd[x,y]:=d;
dd[y,x]:=d;
poto[y]:=x;
xu[i]:=y;
yvu[y]:=true;
for j:=1 to i-1 do
begin
g[xu[j],y]:=g[xu[j],x]+d;
g[y,xu[j]]:=g[xu[j],y];
if g[xu[j],y]>zhijing then
begin
zhijing:=g[xu[j],y];
st:=xu[j];ed:=y;
end;
end;
end;{read in}
{zhijing zhao}
j:=st;i:=0;
while (g[j,ed]>g[poto[j],ed]) and (j<>1) do
begin
inc(i);
long[i]:=j;
j:=poto[j];
end;
q:=j;
j:=ed;
i1:=0;
while j<>q do
begin
inc(i1);
opo[i1]:=j;
j:=poto[j];
end;
inc(i);
long[i]:=q;
for j:=i1 downto 1 do
begin
inc(i);
long[i]:=opo[j];
end;
nl:=i;
{zhao end}
for i:=1 to nl do lin[long[i]]:=true;
if lin[1] then
begin
for j:=1 to n do if not lin[j] then
begin
j1:=j;
sn:=0;
while not lin[j1] do
begin
inc(sn,dd[j1,poto[j1]]);
j1:=poto[j1];
end;
if sn>ri[j1] then ri[j1]:=sn;
end
end
else
begin
ri[q]:=g[1,q];
for j:=2 to n do if not lin[j] then
begin
j1:=j;sn:=0;
while not lin[j1] and (j1<>1) do
begin
inc(sn,dd[j1,poto[j1]]);
j1:=poto[j1];
end;
if j1=1 then
begin
if g[q,j]>ri[q] then ri[q]:=g[q,j]
end
else
if sn>ri[j1] then ri[j1]:=sn;
end;
end;
st:=1;ed:=nl;
while zhijing>s do
begin
x:=ri[long[st]]+dd[long[st],long[st+1]];
y:=ri[long[ed]]+dd[long[ed],long[ed-1]];
if x<y then
begin
inc(st);
if x>ri[long[st]] then ri[long[st]]:=x;
dec(zhijing,dd[long[st-1],long[st]]);
end
else
begin
dec(ed);
if y>ri[long[ed]] then ri[long[ed]]:=y;
dec(zhijing,dd[long[ed],long[ed+1]]);
end;
end;
ans:=0;
for i:=st to ed do if ans<ri[long[i]] then ans:=ri[long[i]];
writeln(ans);
readln
end.
编这么长,我容易吗我....
program boringcore;
var yvu,lin:array[0..300]of boolean;
xu,poto,opo,long,ri:array[0..300]of longint;
g,dd:array[0..300,0..300]of longint;
ans,n,s,i,j,q,x,y,d,nl,i1,zhijing,st,ed,j1,sn:longint;
begin
readln(n,s);
zhijing:=0;
yvu[1]:=true;
xu[1]:=1;i1:=1;
for i:=2 to n do
begin
readln(x,y,d);
dd[x,y]:=d;
dd[y,x]:=d;
if yvu[x] xor yvu[y] then
begin
if yvu[y] then begin q:=x;x:=y;y:=q; end;
poto[y]:=x;
inc(i1);
xu[i1]:=y;
yvu[y]:=true;
end
else
begin
if not yvu[x] then
begin
poto[y]:=x;
inc(i1);xu[i1]:=x;
inc(i1);xu[i1]:=y;
yvu[x]:=true;yvu[y]:=true;
end
else
begin
if poto[y]<>0 then begin q:=x;x:=y;y:=q; end;
poto[y]:=x;
end;
end;
end;
for i:=2 to n do
begin
y:=xu[i];
x:=poto[y];
for j:=1 to i-1 do
begin
g[xu[j],y]:=g[xu[j],x]+dd[x,y];
g[y,xu[j]]:=g[xu[j],x]+dd[x,y];
if g[xu[j],y]>zhijing then
begin
zhijing:=g[xu[j],y];
st:=xu[j];ed:=y;
end;
end;
end; {read in}
{zhijing zhao}
j:=st;i:=0;
while (g[j,ed]>g[poto[j],ed]) and (j<>1) do
begin
inc(i);
long[i]:=j;
j:=poto[j];
end;
q:=j;
j:=ed;
i1:=0;
while j<>q do
begin
inc(i1);
opo[i1]:=j;
j:=poto[j];
end;
inc(i);
long[i]:=q;
for j:=i1 downto 1 do
begin
inc(i);
long[i]:=opo[j];
end;
nl:=i;
{zhao end}
for i:=1 to nl do lin[long[i]]:=true;
if lin[1] then
begin
for j:=1 to n do if not lin[j] then
begin
j1:=j;
sn:=0;
while not lin[j1] do
begin
inc(sn,dd[j1,poto[j1]]);
j1:=poto[j1];
end;
if sn>ri[j1] then ri[j1]:=sn;
end
end
else
begin
ri[q]:=g[1,q];
for j:=2 to n do if not lin[j] then
begin
j1:=j;sn:=0;
while not lin[j1] and (j1<>1) do
begin
inc(sn,dd[j1,poto[j1]]);
j1:=poto[j1];
end;
if j1=1 then
begin
if g[q,j]>ri[q] then ri[q]:=g[q,j]
end
else
if sn>ri[j1] then ri[j1]:=sn;
end;
end;
st:=1;ed:=nl;
while zhijing>s do
begin
x:=ri[long[st]]+dd[long[st],long[st+1]];
y:=ri[long[ed]]+dd[long[ed],long[ed-1]];
if x<y then
begin
inc(st);
if x>ri[long[st]] then ri[long[st]]:=x;
dec(zhijing,dd[long[st-1],long[st]]);
end
else
begin
dec(ed);
if y>ri[long[ed]] then ri[long[ed]]:=y;
dec(zhijing,dd[long[ed],long[ed+1]]);
end;
end;
ans:=0;
for i:=st to ed do if ans<ri[long[i]] then ans:=ri[long[i]];
writeln(ans);
end.
对于我的算法来说,读入很重要,XU数组高效的辅助求最短路径,还有最长直径任选就行