Phá Mã (Gold)

Điểm: 1,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

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây có gốc gồm $N$ đỉnh, đánh số từ $0$ đến $N - 1$ , với đỉnh $0$ là gốc. Mỗi đỉnh $i$ ( $i \geq 1$ ) có cha là $p (i)$ với $p (i) < i$ .

Một "mã khóa" là phép gán mỗi đỉnh một chữ số từ 0 đến 9. Có $M$ ràng buộc cấm, mỗi ràng buộc gồm một đỉnh $v$ và một chuỗi 5 chữ số $s$ . Ràng buộc này cấm các mã khóa mà khi đọc chữ số trên đường đi từ $v$ lên gốc (5 bước), ta thu được chuỗi $s$ .

Cụ thể, nếu đường đi từ $v$ lên gốc đi qua các đỉnh $v, p (v), p (p (v)), p (p (p (v))), p (p (p (p (v))))$ , thì chuỗi chữ số tại 5 đỉnh này không được bằng $s$ .

Đảm bảo rằng mỗi đỉnh có ít nhất 4 tổ tiên (đường đi lên gốc có ít nhất 5 đỉnh).

Hãy đếm số mã khóa bị loại bỏ (vi phạm ít nhất một ràng buộc), modulo $1234567$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ .

$N - 1$ dòng tiếp theo, dòng thứ $i$ chứa $p (i)$ — cha của đỉnh $i$ (với $i$ từ $1$ đến $N - 1$ ).
$M$ dòng tiếp theo, mỗi dòng chứa số nguyên $v$ và chuỗi 5 chữ số $s$ — một ràng buộc cấm.

Dữ liệu ra

Một số nguyên duy nhất — số mã khóa bị loại bỏ, modulo $1234567$ .

Ràng buộc

$1 \leq N \leq 20 000$
$1 \leq M \leq 50 000$
$0 \leq p (i) < i$
$0 \leq v < N$
Chuỗi $s$ có đúng 5 ký tự, mỗi ký tự là chữ số 0-9

Ví dụ

Input	Output	Giải thích
6 2 0 1 2 3 3 4 01234 5 91234	19	Cây có 6 đỉnh. Ràng buộc 1: đường từ đỉnh 4 lên (4→3→2→1→0) không được gán 01234. Ràng buộc 2: đường từ đỉnh 5 lên (5→3→2→1→0) không được gán 91234. Hai ràng buộc chia sẻ phần 1234 ở 4 đỉnh trên, nên có 19 mã khóa bị cấm.

Bình luận

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