1912: [Apio2010]patrol 巡逻
Input
第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b， 表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。
Output
输出一个整数，表示新建了K 条道路后能达到的最小巡逻距离。
Sample Input
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Sample Output
11
HINT
10%的数据中，n ≤ 1000, K = 1；
30%的数据中，K = 1；
80%的数据中，每个村庄相邻的村庄数不超过 25；
90%的数据中，每个村庄相邻的村庄数不超过 150；
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。
Source
分析：
k=0时显然每条边经过一次，答案为2*(n-1)
k=1时可以发现，新路连的两个端点i,j之间形成环，环上所有边都不需要经过两次，相当于k=0时的答案减去ij间距再+1(新路必须经过），显然ij距离最大时最优，故取树上最长链。
k=2时可以发现，在k=1基础上再连一条边不能直接取次长链，因为每经过k=1选取的链上的边，你将会多走2步，故将原来最长链上的边变成-1，再求最长链，在将k=1答案减去+1即可。
program pat;
type
point=^node;
node=record
x,v:longint; next:point;
end;
var
a:array[..]of point;
f1,f2,s1,s2:array[..]of longint;
n,i,m,max,k,x,y,ans:longint; p:point;
procedure add(x,y:longint);
var p:point;
begin
new(p); p^.x:=y; p^.v:=; p^.next:=a[x]; a[x]:=p;
end;
procedure dfs(x,e:longint);
var p:point; y:longint;
begin
s1[x]:=x; s2[x]:=x;
new(p); p:=a[x];
while p<>nil do
begin
y:=p^.x;
if y=e then begin p:=p^.next; continue; end;
dfs(y,x);
if f1[y]+p^.v>f1[x] then
begin
f2[x]:=f1[x]; s2[x]:=s1[x];
f1[x]:=f1[y]+p^.v; s1[x]:=y;
end
else
if f1[y]+p^.v>f2[x] then
begin
f2[x]:=f1[y]+p^.v; s2[x]:=y;
end;
p:=p^.next;
end;
if f1[x]+f2[x]>f1[max]+f2[max] then
max:=x;
end;
procedure work(x:longint);
var p:point; y:longint;
begin
new(p); p:=a[x];
while p<>nil do
begin
y:=p^.x;
if y=s1[x] then begin p^.v:=-; work(y); break; end;
p:=p^.next;
end;
end;
begin
assign(input,'pat.in');reset(input);
assign(output,'pat.out');rewrite(output);
readln(n,k);
for i:= to n- do
begin
readln(x,y); add(x,y); add(y,x);
end;
ans:=*(n-); max:=; f1[]:=; f2[]:=;
dfs(,);
ans:=ans-f1[max]-f2[max]+;
if k= then writeln(ans) else
begin
fillchar(f1,sizeof(f1),);
fillchar(f2,sizeof(f2),);
new(p); p:=a[max];
while p<>nil do
begin
y:=p^.x;
if (y=s1[max])or(y=s2[max]) then p^.v:=-;
p:=p^.next;
end;
work(s1[max]); work(s2[max]); max:=;
dfs(,);
ans:=ans-f1[max]-f2[max]+;
writeln(ans);
end;
close(input); close(output);
end.