#-swank (unless (member :child-sbcl *features*) (quit :unix-status (process-exit-code (run-program *runtime-pathname* `("--control-stack-size" "256MB" "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options" "--eval" "(push :child-sbcl *features*)" "--script" ,(namestring *load-pathname*)) :output t :error t :input t)))) ;; -*- coding: utf-8 -*- (eval-when (:compile-toplevel :load-toplevel :execute) (sb-int:defconstant-eqx OPT #+swank '(optimize (speed 3) (safety 2)) #-swank '(optimize (speed 3) (safety 0) (debug 0)) #'equal) #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t) #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t)))) #+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax) #-swank (disable-debugger) ; for CS Academy ;; BEGIN_INSERTED_CONTENTS ;; Should we do this with UNWIND-PROTECT? (defmacro with-buffered-stdout (&body body) "Buffers all outputs to *STANDARD-OUTPUT* in BODY and flushes them to *STANDARD-OUTPUT* after BODY has been done (without error). Note that only BASE-CHAR is allowed." (let ((out (gensym))) `(let ((,out (make-string-output-stream :element-type 'base-char))) (let ((*standard-output* ,out)) ,@body) (write-string (get-output-stream-string ,out))))) (defmacro define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits) ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits))) (define-int-types 2 4 7 8 15 16 31 32 62 63 64) (declaim (ftype (function * (values fixnum &optional)) read-fixnum)) (defun read-fixnum (&optional (in *standard-input*)) (declare #.OPT) (macrolet ((%read-byte () `(the (unsigned-byte 8) #+swank (char-code (read-char in nil #\Nul)) #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil)))) (let* ((minus nil) (result (loop (let ((byte (%read-byte))) (cond ((<= 48 byte 57) (return (- byte 48))) ((zerop byte) ; #\Nul (error "Read EOF or #\Nul.")) ((= byte #.(char-code #\-)) (setf minus t))))))) (declare ((integer 0 #.most-positive-fixnum) result)) (loop (let* ((byte (%read-byte))) (if (<= 48 byte 57) (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result)))) (return (if minus (- result) result)))))))) ;;; ;;; Lowest common ancestor of tree by binary lifting ;;; build: O(nlog(n)) ;;; query: O(log(n)) ;;; ;; PAY ATTENTION TO THE STACK SIZE! BUILD-LCA-TABLE does DFS. (deftype lca-vertex-number () '(signed-byte 32)) (defstruct (lca-table (:constructor make-lca-table (size &aux ;; requires 1 + log_2{size-1} (max-level (+ 1 (integer-length (- size 2)))) (depths (make-array size :element-type 'lca-vertex-number)) (parents (make-array (list size max-level) :element-type 'lca-vertex-number)) (weights (make-array size :element-type '(unsigned-byte 62) :initial-element 0)))) (:conc-name lca-)) (max-level nil :type (integer 0 #.most-positive-fixnum)) (depths nil :type (simple-array lca-vertex-number (*))) (parents nil :type (simple-array lca-vertex-number (* *))) (weights nil :type (simple-array (unsigned-byte 62) (*)))) (defun build-lca-table (root graph) "GRAPH := vector of adjacency lists" (declare #.OPT ((simple-array list (*)) graph)) (let* ((size (length graph)) (lca-table (make-lca-table size)) (depths (lca-depths lca-table)) (weights (lca-weights lca-table)) (parents (lca-parents lca-table)) (max-level (lca-max-level lca-table))) (labels ((dfs (v prev-v depth weight) (declare (lca-vertex-number v prev-v) (uint62 weight)) (setf (aref depths v) depth) (setf (aref weights v) weight) (setf (aref parents v 0) prev-v) (dolist (node (aref graph v)) (let ((dest (car node)) (dweight (cdr node))) (declare (lca-vertex-number dest) (uint62 dweight)) (unless (= dest prev-v) (dfs dest v (+ 1 depth) (+ weight dweight))))))) (dfs root -1 0 0) (dotimes (k (- max-level 1)) (dotimes (v size) (if (= -1 (aref parents v k)) (setf (aref parents v (+ k 1)) -1) (setf (aref parents v (+ k 1)) (aref parents (aref parents v k) k))))) lca-table))) (defun get-lca (u v lca-table) "Returns the lowest common ancestor of the vertices U and V." (declare #.OPT (lca-vertex-number u v)) (let* ((depths (lca-depths lca-table)) (parents (lca-parents lca-table)) (max-level (lca-max-level lca-table))) ;; Ensures depth[u] <= depth[v] (when (> (aref depths u) (aref depths v)) (rotatef u v)) (dotimes (k max-level) (when (logbitp k (- (aref depths v) (aref depths u))) (setf v (aref parents v k)))) (if (= u v) u (loop for k from (- max-level 1) downto 0 unless (= (aref parents u k) (aref parents v k)) do (setf u (aref parents u k) v (aref parents v k)) finally (return (aref parents u 0)))))) (defmacro dbg (&rest forms) #+swank (if (= (length forms) 1) `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms)) `(format *error-output* "~A => ~A~%" ',forms `(,,@forms))) #-swank (declare (ignore forms))) (declaim (inline println)) (defun println (obj &optional (stream *standard-output*)) (let ((*read-default-float-format* 'double-float)) (prog1 (princ obj stream) (terpri stream)))) (defconstant +mod+ 1000000007) ;;; ;;; Body ;;; (defun main () (declare #.OPT) (let* ((n (read)) ;; to . weight (graph (make-array n :element-type 'list :initial-element nil))) (declare (uint31 n)) (dotimes (i (- n 1)) (let ((u (read-fixnum)) (v (read-fixnum)) (w (read-fixnum))) (push (cons u w) (aref graph v)) (push (cons v w) (aref graph u)))) (let* ((table (build-lca-table 0 graph)) (q (read))) (declare (uint31 q)) (labels ((calc-dist (u v) (declare (values uint62)) (let ((weights (lca-weights table)) (lca (get-lca u v table))) (- (+ (aref weights u) (aref weights v)) (* 2 (aref weights lca)))))) (with-buffered-stdout (dotimes (_ q) (let* ((x (read-fixnum)) (y (read-fixnum)) (z (read-fixnum))) (println (floor (+ (calc-dist x y) (calc-dist y z) (calc-dist z x)) 2))))))))) #-swank (main)