BZOJ1912:[APIO2010]patrol巡逻

Description

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

Sample Output

11

HINT

10%的数据中，n ≤ 1000, K = 1； 
30%的数据中，K = 1； 
80%的数据中，每个村庄相邻的村庄数不超过 25； 
90%的数据中，每个村庄相邻的村庄数不超过 150； 
100%的数据中，3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

 

题解：

对于新建的k条边，求出在原树上的k条路径；若其无重复边，则优化长度为路径长度和；若有重复，则重复部分不被优化，优化的部分也可以表示为两条不重复路径。

问题变成了在树上求k条边不重复路径，使总距离最长。

若k=1，则该路径为树的直径；

若k=2，可以证明，两条路径只有两种可能：

1.一条为直径，一条与直径无重复。

2.两条都与直径有重复。

这样，只要先求一次直径，将直径上的边权值赋为-1，再求一次直径，将结果相加即可。

 

代码：

type
  point=^node;
   node=record
      x,v:longint; next:point;
   end;
var
  a:array[0..100000]of point;
  f1,f2,s1,s2:array[0..100000]of longint;
  n,i,m,max,k,x,y,ans:longint; p:point;
procedure ss(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;
    ss(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 add(x,y:longint);
var p:point;
begin
  new(p); p^.x:=y; p^.v:=1; p^.next:=a[x]; a[x]:=p;
end;
procedure qq(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:=-1; qq(y); break; end;
     p:=p^.next;
   end;
end;
begin
  readln(n,k);
  for i:=1 to n-1 do
   begin
     readln(x,y); add(x,y);  add(y,x);
   end;
  ans:=2*(n-1); max:=0; f1[0]:=0; f2[0]:=0;
  ss(1,0);
  ans:=ans-f1[max]-f2[max]+1;
  if k=1 then writeln(ans) else
  begin
    fillchar(f1,sizeof(f1),0);
    fillchar(f2,sizeof(f2),0);
    new(p); p:=a[max];
    while p<>nil do
    begin
      y:=p^.x;
      if (y=s1[max])or(y=s2[max]) then p^.v:=-1;
      p:=p^.next;
    end;
    qq(s1[max]); qq(s2[max]);  max:=0;
    ss(1,0);
    ans:=ans-f1[max]-f2[max]+1;
    writeln(ans);
  end;
end.