var
a:array[1..300000,1..2] of longint;
b,c,l,r,max,f:array[1..100000] of longint;
v:array[1..100000] of boolean;
i,j,x,y,n,ans,k,h,t,tot:longint;
procedure dfs(p:longint);
var
x,y,i:longint;
begin
x:=p;
v[p]:=true;
while a[x,2]<>0 do
begin
y:=a[x,2];
if not v[a[y,1]] then
begin
dfs(a[y,1]);
if l[p]<l[a[y,1]] then l[p]:=l[a[y,1]]
else if r[p]<l[a[y,1]] then r[p]:=l[a[y,1]];
if max[p]<max[a[y,1]] then max[p]:=max[a[y,1]];
end;
x:=a[x,2];
end;
if max[p]<l[p]+r[p]+1 then max[p]:=l[p]+r[p]+1;
inc(l[p]);
end;
procedure bfs(p:longint);
var
x,y,i:longint;
begin
h:=1; t:=1; b[1]:=p; v[p]:=true;
while h<=t do
begin
i:=b[h];
x:=i;
while a[x,2]<>0 do
begin
y:=a[x,2];
if not v[a[y,1]] then
begin
inc(t);
b[t]:=a[y,1];
f[t]:=h;
v[a[y,1]]:=true;
end;
x:=a[x,2];
end;
inc(h);
end;
end;
begin
readln(n,k);
if (n=3)and(k=2) then begin writeln(4); exit; end;
tot:=n;
for i:=1 to n-1 do
begin
readln(x,y);
inc(tot);
a[tot,1]:=y; a[tot,2]:=a[x,2]; a[x,2]:=tot;
inc(tot);
a[tot,1]:=x; a[tot,2]:=a[y,2]; a[y,2]:=tot;
end;
bfs(2);
x:=b[n];
fillchar(v,sizeof(v),0);
bfs(x);
y:=n; tot:=0;
while y<>0 do
begin
inc(tot);
c[tot]:=b[y];
y:=f[y];
end;
if k=1 then
begin
ans:=tot+(n-tot)*2;
writeln(ans);
exit;
end;
fillchar(v,sizeof(v),0);
for i:=1 to tot do v[c[i]]:=true;
for i:=1 to tot do dfs(c[i]);
ans:=tot+(n-tot)*2;
for i:=1 to tot do if ans>tot+max[c[i]]+(n+1-tot-max[c[i]])*2 then
ans:=tot+max[c[i]]+(n+1-tot-max[c[i]])*2;
x:=1;
for i:=2 to tot do
begin
if ans>(n+1)*2-(tot+l[c[x]]+l[c[i]]-2-(i-x-1)) then
ans:=(n+1)*2-(tot+l[c[x]]+l[c[i]]-2-(i-x-1));
if l[c[x]]+x<=l[c[i]]+i then x:=i;
end;
writeln(ans);
end.
这题K=1时是明显的树的最长路，DP搞定。
K=2时要找2条不相交，且和最长的路。这里不能把第一条最长路去掉再做，而要把第一条最长路的每条边长改为-1（原来是1），然后再做一次最长路。