trang chủ / đề bài / icpcwf19_g

Tên của nàng

Đề bài

Mô tả

Trong Hoàng tộc, tên gọi là điều vô cùng quan trọng! Là Sử gia Hoàng gia, bạn được giao nhiệm vụ phân tích các quy luật trong tên của các Công nương trong vương quốc.

Đã có n Công nương, để tiện ta đánh số từ 1 đến n. Tên của mỗi Công nương là một chữ cái in hoa ghép với tên của mẹ cô. Ngoại lệ duy nhất là Công nương số 1, người sáng lập Hoàng tộc, có tên chỉ gồm một chữ cái in hoa.

Ví dụ, ENERYS có thể là mẹ của AENERYS (vì tên AENERYS gồm chữ cái in hoa A ghép với ENERYS, tên của mẹ cô). Tương tự, AENERYS có thể là mẹ của DAENERYS và YAENERYS.

Cho mô tả của tất cả các Công nương. Nhiệm vụ của bạn là xác định, với một số xâu s đáng chú ý, số Công nương có s là tiền tố của tên mình.

Ví dụ, xét ví dụ thứ nhất dưới đây: dòng dõi đi thẳng từ người sáng lập S tới AENERYS (qua YS, RYS, ERYS, NERYS và ENERYS), mỗi Công nương có đúng một con gái. Sau đó AENERYS có hai con gái là DAENERYS và YAENERYS, và YAENERYS có một con gái là RYAENERYS.

tree parent
1 2 3 4 5 6 7 7 9
label 1 S
label 2 YS
label 3 RYS
label 4 ERYS
label 5 NERYS
label 6 ENERYS
label 7 AENERYS
label 8 DAENERYS
label 9 YAENERYS
label 10 RYAENERYS

Trong Hoàng tộc này, RY là tiền tố của tên hai Công nương: RYS và RYAENERYS. E là tiền tố của tên ERYS và ENERYS. N chỉ là tiền tố của tên NERYS, còn S chỉ là tiền tố của tên người sáng lập S. AY không là tiền tố của tên Công nương nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k, trong đó n là tổng số Công nương và k là số xâu truy vấn.

Tiếp theo là n dòng mô tả các Công nương. Dòng thứ i mô tả Công nương số i, gồm một chữ cái in hoa ci (từ A đến Z) và một số nguyên pi, trong đó ci là chữ cái đầu tiên trong tên Công nương i, còn pi là số hiệu của mẹ cô (hoặc 0 với Công nương đầu tiên). Tên của tất cả các Công nương đôi một khác nhau.

k dòng còn lại, mỗi dòng chứa một xâu truy vấn khác rỗng chỉ gồm các chữ cái in hoa.

Dữ liệu ra

In ra k dòng, dòng thứ i chứa số Công nương có xâu truy vấn thứ i là tiền tố của tên mình.

Ràng buộc

  • 1≤n≤106.
  • 1≤k≤106.
  • p1=0 và 1≤pi<i với i>1.
  • Tổng độ dài các xâu truy vấn không vượt quá 106.

Ví dụ

Input Output Giải thích
10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY
2
2
1
1
0
Hoàng tộc trong hình trên. RY là tiền tố của RYS và RYAENERYS; E là tiền tố của ERYS và ENERYS; N chỉ của NERYS; S chỉ của S; AY không của ai.
8 3
C 0
A 1
E 1
A 3
D 1
B 3
C 4
B 6
EA
CB
A
0
0
2
Tên các Công nương lần lượt là C, AC, EC, AEC, DC, BEC, CAEC, BBEC. Không tên nào bắt đầu bằng EA hay CB; A là tiền tố của AC và AEC.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0