Lorenzo Von Matterhorn

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Xét một cây nhị phân vô hạn với các đỉnh được đánh số bằng số nguyên dương bắt đầu từ $1$ . Với mỗi số nguyên dương $i$ , tồn tại một cạnh hai chiều giữa đỉnh $i$ và đỉnh $2 i$ , và một cạnh hai chiều giữa đỉnh $i$ và đỉnh $2 i + 1$ . Giữa hai đỉnh bất kì, đường đi ngắn nhất là duy nhất.

Ban đầu mọi cạnh có phí qua đường bằng $0$ . Bạn cần xử lý $q$ sự kiện theo thứ tự, mỗi sự kiện thuộc một trong hai loại:

Loại 1: Cho ba số nguyên $v$ , $u$ , $w$ . Phí qua đường của mọi cạnh trên đường đi ngắn nhất giữa $u$ và $v$ tăng thêm $w$ .
Loại 2: Cho hai số nguyên $v$ , $u$ . Hãy tính tổng phí qua đường của mọi cạnh trên đường đi ngắn nhất giữa $u$ và $v$ .

Dữ liệu vào

Dòng đầu chứa một số nguyên $q$ — số sự kiện.
q dòng tiếp theo mô tả các sự kiện theo thứ tự. Mỗi dòng bắt đầu bằng loại sự kiện:
- 1 v u w cho sự kiện loại 1.
- 2 v u cho sự kiện loại 2.

Dữ liệu ra

Với mỗi sự kiện loại 2, in ra một dòng chứa tổng phí cần trả.

Ràng buộc

$1 \leq q \leq 1000$
$1 \leq v, u \leq 10^{18}$ , $v \neq u$
$1 \leq w \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
7 1 3 4 30 1 4 1 2 1 3 6 8 2 4 3 1 6 1 40 2 3 7 2 2 4	94 0 32	Sau ba sự kiện loại 1 đầu tiên, đường đi từ $4$ đến $3$ gồm các cạnh $4 - 2$ , $2 - 1$ , $1 - 3$ với phí lần lượt $32$ , $32$ , $30$ , tổng $94$ . Đường $3 - 7$ không chia sẻ cạnh nào đã tăng phí nên trả $0$ . Sau sự kiện loại 1 thứ tư, đường $2 - 4$ chỉ gồm cạnh $4 - 2$ với phí $32$ .
2 1 4294967298 4294967299 10 2 2 3	0	Đường giữa $4294967298$ và $4294967299$ không đi qua các cạnh $1 - 2$ hay $1 - 3$ , nên truy vấn cuối trả $0$ .

Bình luận

Không có bình luận tại thời điểm này.