BZOJ 1787: [Ahoi2008]Meet 紧急集合（lca+贪心）

[Ahoi2008]Meet 紧急集合

Description

Input

Output

Sample Input

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

Sample Output

5 2

2 5

4 1

6 0
HINT

分析：很简单的一道题，对于每次询问要分情况讨论，先求出两两之间的lca，如果为同一点，显然该点为集合点，如果有一个x不同于另外两个，则三者在一条链上，x为中间的一个，故x为集合点，如果三者互不相同，集合点可以是三者到共同lca路径上任何一点，或者干脆将三者共同lca作为集合点就行了。

代码：

program Meet;

type

  point=^node;

    node=record

       x:longint; next:point;

    end;

var

  a:array[..]of point;

  f:array[..,..]of longint;

  deep,s:array[..]of longint;

  n,i,m,x,y,t,z,v1,v2,v3,ans:longint;

procedure add(x,y:longint);

var p:point;

begin

  new(p); p^.x:=y; p^.next:=a[x]; a[x]:=p;

end;

procedure dfs(x,k:longint);

var p:point;

begin

  new(p); p:=a[x];  f[,x]:=k; deep[x]:=deep[k]+;

  while p<>nil do

   begin

     if p^.x<>k then dfs(p^.x,x);p:=p^.next;

   end;

end;

procedure work;

var i,j:longint;

begin

  for i:= to trunc(ln(n)/ln())- do

   for j:= to n do

    f[i+,j]:=f[i,f[i,j]];

end;

function lca(x,y:longint):longint;

var i,t:longint;

begin

  if deep[x]<deep[y] then begin t:=x; x:=y; y:=t; end;

  for i:= to trunc(ln(n)/ln()) do

   if ((deep[x]-deep[y])>>i) and = then x:=f[i,x];

  if x=y then exit(x);

  for i:=trunc(ln(n)/ln()) downto  do

   if f[i,x]<>f[i,y] then

    begin x:=f[i,x]; y:=f[i,y]; end;

  exit(f[,x]);

end;

begin

  assign(input,'Meet.in');

reset(input);

assign(output,'Meet.out');

rewrite(output);

  readln(n,m);

  for i:= to n- do

   begin

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

   end;

  deep[]:=;

  dfs(,);  work;

  for i:= to m do

   begin

     readln(x,y,z);

     v1:=lca(x,y);  v2:=lca(x,z); v3:=lca(z,y);

     if (v1=v2)and(v2=v3) then t:=v1

      else if v1=v2 then t:=v3

       else if v2=v3 then t:=v1

        else t:=v2;

     v1:=lca(x,t); v2:=lca(y,t); v3:=lca(z,t);

     ans:=deep[x]+deep[y]+deep[z]+deep[t]*-*(deep[v1]+deep[v2]+deep[v3]);

     writeln(t,' ',ans);

   end;

  close(input); close(output);

end.

巴特西

BZOJ 1787: [Ahoi2008]Meet 紧急集合（lca+贪心）

最新文章

热门文章