Submission #39381925

---

Source Code Expand

let subtree_size al =
  let ss = Array.make (Array.length al) 1 in
  let rec loop p i =
    List.iter (fun j ->
      if j <> p then begin
        loop i j;
        ss.(i) <- ss.(i) + ss.(j)
      end
    ) al.(i) in
  let () = loop (-1) 0 in
  ss

let centroid_decomp al ss =
  let pl = Array.make (Array.length al) (-2) in
  let rec decomp p i pc n =
    (* j <> p: 下から上に行かない *)
    (* pl.(j) = -2: すでに見つけた重心は無視する *)
    let j = List.find_opt (fun j -> j <> p && pl.(j) = -2 && ss.(j) * 2 > n) al.(i) in
    match j with
    | Some j ->
      ss.(i) <- n - ss.(j);
      decomp i j pc n
    | None ->
      pl.(i) <- pc;
      List.iter (fun j -> if pl.(j) = -2 then decomp i j i ss.(j)) al.(i) in
  let () = decomp (-1) 0 (-1) (Array.length al) in
  pl

let () =
  let n = Scanf.scanf " %d" Fun.id in
  let al = Array.make n [] in
  let () =
    for i = 1 to n - 1 do
      Scanf.scanf " %d %d" (fun a b -> 
        let a = a - 1 in
        let b = b - 1 in
        al.(a) <- b :: al.(a);
        al.(b) <- a :: al.(b))
    done in
  let pl = subtree_size al |> centroid_decomp al in
  for i = 0 to n - 1 do
    let p = pl.(i) in
    let p = if p >= 0 then p + 1 else p in
    print_int p;
    if i < n - 1 then
      print_char ' '
    else
      print_newline()
  done

Submission Info

Judge Result