Submission #24778992

---

Source Code Expand

(** val half : int -> int **)

let rec half = (Fun.flip ( lsr ) 1)

(** val climb : (int -> 'a1 -> 'a1) -> int -> int -> int -> 'a1 -> 'a1 **)

let rec climb climb2exp e p n v =
  (fun fO fS n -> if n = 0 then fO () else fS (n-1))
    (fun _ -> v)
    (fun e' ->
    let p' = half p in
    if ( <= ) (succ n) p'
    then climb climb2exp e' p' n v
    else climb climb2exp e' p' (( - ) n p') (climb2exp e' v))
    e

(** val bisect :
    ('a1 -> 'a1 -> bool) -> (int -> 'a1 -> 'a1) -> int -> 'a1 -> 'a1 -> 'a1 **)

let rec bisect eq_vertex climb2exp e u v =
  (fun fO fS n -> if n = 0 then fO () else fS (n-1))
    (fun _ -> climb2exp 0 u)
    (fun e' ->
    let u' = climb2exp e' u in
    let v' = climb2exp e' v in
    if eq_vertex u' v'
    then bisect eq_vertex climb2exp e' u v
    else bisect eq_vertex climb2exp e' u' v')
    e

(** val lca_aux :
    ('a1 -> 'a1 -> bool) -> (int -> 'a1 -> 'a1) -> int -> 'a1 -> 'a1 -> 'a1 **)

let lca_aux eq_vertex climb2exp e u v =
  if eq_vertex u v then u else bisect eq_vertex climb2exp e u v

(** val lca :
    ('a1 -> 'a1 -> bool) -> ('a1 -> int) -> (int -> 'a1 -> 'a1) -> int -> int
    -> 'a1 -> 'a1 -> 'a1 **)

let lca eq_vertex height climb2exp e p u v =
  if ( <= ) (height u) (height v)
  then lca_aux eq_vertex climb2exp e u
         (climb climb2exp e p (( - ) (height v) (height u)) v)
  else lca_aux eq_vertex climb2exp e v
         (climb climb2exp e p (( - ) (height u) (height v)) u)

let bits = 62

let () = Scanf.scanf "%d\n" @@ fun n ->
  let es = Array.make n [] in
  for i = 0 to n - 2 do
    Scanf.scanf "%d %d\n" @@ fun x y ->
      es.(x - 1) <- y - 1 :: es.(x - 1);
      es.(y - 1) <- x - 1 :: es.(y - 1)
  done;
  let hs = Array.make n max_int in
  let pss = Array.make_matrix bits n 0 in
  let rec visit h u v =
    if h < hs.(v) then (
      hs.(v) <- h;
      pss.(0).(v) <- u;
      List.iter (visit (h + 1) v) es.(v)
    ) in
  visit 0 0 0;
  for i = 0 to bits - 2 do
    for v = 0 to n - 1 do
      pss.(i + 1).(v) <- pss.(i).(pss.(i).(v))
    done
  done;
  Scanf.scanf "%d\n" @@ fun q ->
    for i = 0 to q - 1 do
      Scanf.scanf "%d %d\n" @@ fun a b ->
        Printf.printf "%d\n" @@
        1 + hs.(a - 1) + hs.(b - 1) - 2 * hs.(lca ( = ) (Array.get hs) (fun i v -> pss.(i).(v)) bits (1 lsl bits) (a - 1) (b - 1))
    done

Submission Info

Judge Result