Cây XOR

Đ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

Cho một cây có $n$ đỉnh, đánh số từ $1$ đến $n$ , gốc tại đỉnh $1$ . Mỗi đỉnh $i$ có một giá trị ban đầu $i n i t_{i} \in {0, 1}$ .

Một thao tác được định nghĩa như sau: chọn một đỉnh $x$ . Khi đó:

Giá trị của $x$ bị đảo ( $0 \leftrightarrow 1$ ).
Các con (cách $x$ một cạnh) của $x$ giữ nguyên.
Các cháu (cách $x$ hai cạnh) bị đảo.
Cứ tiếp tục như vậy: ở khoảng cách chẵn so với $x$ thì đảo, ở khoảng cách lẻ thì giữ nguyên.

Hãy đưa giá trị của mỗi đỉnh $i$ về đúng $g o a l_{i} \in {0, 1}$ bằng số thao tác ít nhất.

Dữ liệu vào

Dòng đầu: số nguyên $n$ .
$n - 1$ dòng tiếp theo: hai số $u_{i}, v_{i}$ — một cạnh của cây.
Dòng tiếp theo: $n$ số $i n i t_{1}, i n i t_{2}, \dots, i n i t_{n}$ .
Dòng cuối: $n$ số $g o a l_{1}, g o a l_{2}, \dots, g o a l_{n}$ .

Dữ liệu ra

Dòng đầu: số nguyên $c n t$ — số thao tác tối thiểu.
$c n t$ dòng tiếp theo: mỗi dòng một số $x_{i}$ — đỉnh được chọn ở thao tác thứ $i$ .

Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ. Thứ tự thực hiện các thao tác không ảnh hưởng đến kết quả cuối cùng.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$
$i n i t_{i}, g o a l_{i} \in {0, 1}$
Các cạnh tạo thành một cây có gốc tại đỉnh $1$ .

Ví dụ

Input	Output	Giải thích
10 2 1 3 1 4 2 5 1 6 2 7 5 8 6 9 8 10 5 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1	2 7 4	Chọn $x = 7$ : đỉnh $7$ bị đảo (từ $0$ thành $1$ ). Chọn $x = 4$ : đỉnh $4$ bị đảo (từ $1$ thành $0$ ). Sau hai thao tác, tất cả các đỉnh đạt đúng giá trị mục tiêu. Thứ tự in các đỉnh không quan trọng vì có nhiều phương án hợp lệ.
1 0 0	0	Đã đạt mục tiêu, không cần thao tác nào.
15 2 1 3 1 4 1 5 1 6 3 7 1 8 1 9 1 10 5 11 9 12 3 13 5 14 5 15 4 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0	6 14 10 4 3 6 2	Một phương án tối ưu gồm $6$ thao tác tại tập đỉnh ${2, 3, 4, 6, 10, 14}$ . Thứ tự liệt kê không ảnh hưởng đến kết quả.

Bình luận

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