C11BC2 – spoj

Đề bài:

• http://vn.spoj.com/problems/C11BC2/

Thuật toán:

• Bài này chỉ cần LCA thôi. Dễ mà bạn tự nghĩ sẽ ra…

Code:

• xem code trên ideone

const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxm=trunc(1e5);
  maxp=20;
var
  link,head,ke,ts : array[-maxm..maxm] of longint;
  i,j,n,m,x,y,q,qq : longint;
  depth,cha,cau : array[1..maxn] of longint;
  p : array[1..maxn,0..maxp] of longint;
  ok : array[1..maxn,0..maxp] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v,w : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
    ts[i] := w;
  end;
procedure enter;
  var u,v ,w :longint;
  begin
    assign(input,fi);reset(input);
    readln(n,q);
    for i:=2 to n do
      begin
        read(v,w);
        add(i,i,v,w);
        add(-i,v,i,w);
      end;
  end;
procedure dfs(u : longint);
  var i,j,v : longint;
  begin
    cx[u] := false;
    i:=head[u];
    while i<>0 do
      begin
        v:=ke[i];
        if cx[v] then
        begin
          cau[v] := i;
          cha[v] := u;
          depth[v] := depth[u]+1;
          dfs(v);
        end;
        i:=link[i];
      end;
  end;
procedure init;
  var i,u : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    cha[1] := 1;
    depth[1] := 1;
    dfs(1);
    for i:=1 to n do
      begin
        p[i,0] := cha[i];
        if cau[i]<>0 then
          if ts[cau[i]]=2 then
            ok[i,0] := true;
      end;
      for i:=1 to maxp do
      for u:=1 to n do
        begin
          p[u,i] := p[p[u,i-1],i-1];
          ok[u,i] := ok[u,i] or ok[u,i-1] or ok[p[u,i-1],i-1];
        end;
  end;
function lca ( u,v : longint) : boolean;
  var res : boolean;
  begin
    res := false;
    for i:=maxp downto 0 do
      if depth[p[u,i]]>=depth[v] then
        begin
          res := res or ok[u,i];
          u := p[u,i];
        end;
    for i:=maxp downto 0 do
      if depth[p[v,i]]>=depth[u] then
        begin
          res := res or ok[v,i];
          v := p[v,i];
        end;
    if u=v then
      begin
        //writeln(u);
        exit(res);
      end;
        for i:=maxp downto 0 do
          if p[u,i]<>p[v,i] then
          begin
            res := res or ok[u,i];
            res := res or ok[v,i];
            u := p[u,i];
            v := p[v,i];
          end;
    res := res or (ok[u,0]) or (ok[v,0]);
    //writeln(cha[u]);
    exit(res);
end;
procedure process;
  var x,y : longint;
  begin
    assign(output,fo);rewrite(output);
    for qq := 1 to q do
      begin
        read(x,y);
        if lca(x,y) then writeln('YES') else writeln('NO');
      end;
    close(output);
  end;
begin
  enter;
  init;
  process;
end.