Hẹn hò

Điểm: 8,00 (OI)

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

Python 3 5.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

Có $n$ ngôi nhà được đánh số từ $1$ đến $n$ , được nối với nhau bởi $n - 1$ con đường hai chiều sao cho tạo thành một cây (giữa hai ngôi nhà bất kỳ có đúng một đường đi đơn).

Mỗi ngôi nhà $i$ có hai thuộc tính:

Giới tính $g_{i} \in {0, 1}$ (giá trị $1$ là con trai, giá trị $0$ là con gái).
Số yêu thích $f_{i}$ ( $1 \leq f_{i} \leq 10^{9}$ ).

Cho $q$ truy vấn, mỗi truy vấn gồm hai số $a$ và $b$ . Với mỗi truy vấn, hãy đếm số cặp không có thứ tự $(u, v)$ sao cho cả $u$ và $v$ đều nằm trên đường đi đơn từ $a$ đến $b$ , đồng thời $g_{u} \neq g_{v}$ và $f_{u} = f_{v}$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ ( $1 \leq n \leq 10^{5}$ ).
Dòng thứ hai chứa $n$ số nguyên $g_{1}, g_{2}, \dots, g_{n}$ , mỗi số là $0$ hoặc $1$ .
Dòng thứ ba chứa $n$ số nguyên $f_{1}, f_{2}, \dots, f_{n}$ ( $1 \leq f_{i} \leq 10^{9}$ ).
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ và $b_{i}$ ( $1 \leq a_{i}, b_{i} \leq n$ ) mô tả một cạnh của cây.
Dòng tiếp theo chứa số nguyên $q$ ( $1 \leq q \leq 10^{5}$ ).
$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ ( $1 \leq a, b \leq n$ ) mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là đáp án của một truy vấn theo thứ tự đề bài.

Ràng buộc

$1 \leq n, q \leq 10^{5}$
$1 \leq f_{i} \leq 10^{9}$
Đồ thị đề bài cho là một cây liên thông.

Ví dụ

Input	Output	Giải thích
7 1 0 0 1 0 1 0 9 2 9 2 2 9 9 2 6 1 2 4 2 6 5 3 6 7 4 2 1 3 7 5	2 3	Truy vấn 1: đường đi $1 \to 2 \to 6 \to 3$ . Các cặp hợp lệ là $(1, 3)$ và $(6, 3)$ . Truy vấn 2: đường đi $7 \to 4 \to 2 \to 6 \to 5$ . Các cặp hợp lệ là $(7, 6)$ , $(4, 2)$ , $(4, 5)$ .
4 0 1 1 1 2 5 8 4 1 4 2 4 3 4 6 2 3 1 3 3 4 1 4 2 4 1 4	0 0 0 0 0 0	Không tồn tại cặp nào có cùng số yêu thích và khác giới tính trên các đường đi.
7 0 1 0 1 0 1 0 2 1 2 1 1 1 2 3 1 3 2 3 4 3 5 3 6 3 7 7 1 2 4 2 5 2 6 2 3 2 7 2 3 2	0 0 1 0 0 0 0	Chỉ truy vấn $5 \to 2$ có một cặp hợp lệ là $(5, 2)$ với $f_{5} = f_{2} = 1$ và $g_{5} = 0, g_{2} = 1$ .

Bình luận

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