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

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[..]of point;

   f1,f2,s1,s2:array[..]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:=; 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:=-; qq(y); break; end;

      p:=p^.next;

    end;

 end;

 begin

   readln(n,k);

   for i:= to n- do

    begin

      readln(x,y); add(x,y);  add(y,x);

    end;

   ans:=*(n-); max:=; f1[]:=; f2[]:=;

   ss(,);

   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;

     qq(s1[max]); qq(s2[max]);  max:=;

     ss(,);

     ans:=ans-f1[max]-f2[max]+;

     writeln(ans);

   end;

 end.

巴特西