Background

NOIP2018 Original Mock Test T6
NOIP2018 Original Mock Test DAY2 T3
NOIP DAY1 T3+ or DAY2 T3 Difficulty

Given the difficulty of NOIP2017 DAY2 T3, this problem was created. However, this problem does not test knowledge of suffix automata.

Problem Description

Xiao P is a highly skilled programmer who has developed his own operating system called PION. This system is significantly different from Windows and Linux. Currently, he is testing the system.

The major difference between the PION system and Windows lies in file storage and operations. In PION, folders do not have parent-child relationships. In Windows, one can create subfolders within folders. However, PION folders do not differentiate between parent and child, but some folders can directly access each other. We call this relationship mutual access. For a system with $n$ folders, there are $n-1$ mutual access relationships, ensuring that all folders can access each other through these relationships. In other words, we can view the set of folders in Windows as a rooted tree, while the set of folders in PION as an unrooted tree.

In the PION system, each folder can store files, just like in Windows, where filenames include suffixes.

Xiao P is now conceptualizing an interactive program called dmc, which he refers to as the PION Suffix Automaton, to facilitate operations on file suffixes in folders. Being very busy, he hopes you can help him implement some functionalities.

He wants you to implement three functionalities:

1. Calculate the distance between two folders. We define the distance as the minimum number of mutual accesses required for one folder to reach another. For example, the distance between the same folder is 0, and between two folders with mutual access, it is 1.

2. Calculate the number of files with suffix A in the folders along the path between two folders (including these two folders), where A is a lowercase string. Hint: We can understand the path between PION folders as the path between two nodes in a tree.

3. Delete files with suffix A in the folders along the path between two folders (including these two folders) and count the number of deleted files.

Since dmc is an interactive system, we describe these operations using tab language:

query /p u v

Indicates operation one, where $u, v$ represent the folder IDs.

query /e u v *.A

Indicates operation two, where $u, v$ represent the folder IDs, $'*'$ is a wildcard, $'.'$ is used to separate the filename and suffix, and A is a lowercase string.

del /e u v *.A

Indicates operation three, where $u, v, *.A$ have the same meaning as in operation two.

If you did not understand the problem, please refer to the sample and sample explanation for clarification.

This challenging task is now entrusted to you.

Input Format

The first line contains two numbers, $n, m$, where $n$ is the number of folders (folder IDs range from $[1, n]$) and $m$ is the number of operations.

The next $n-1$ lines each contain two numbers $u, v$, indicating a mutual access relationship between folders $u$ and $v$.

The next $n$ lines, the $i$-th line starts with a number $k$, indicating the $i$-th folder has $k$ files, followed by $k$ strings representing the suffixes of each file.

The next $m$ lines each contain a command string, formatted as described above.

Output Format

For each command, output a number, the meaning of which is described above.

Sample Input and Output

Input Sample #1

5 5
1 2
2 4
2 5
1 3
2 cpp c
3 pas txt txt
2 vbs bat
3 vbs cpp pas
4 cpp c pas txt
query /e 1 5 *.txt
query /p 1 4
del /e 2 2 *.txt
query /e 1 5 *.txt
query /e 4 3 *.vbs

Output Sample #1

3
2
2
1
2

Input Sample #2

12 7
1 2
1 3
1 4
2 5
2 6
3 7
7 12
8 4
8 9
10 9
11 9
0
2 c c
3 zz c c
0
1 gif
2 png bmp
3 avl avl mpshi
0
4 cpp c pas js
5 a b c d e
0
3 a b c
query /p 11 12
query /e 1 2 *.gif
query /e 6 10 *.c
del /e 2 9 *.c
del /e 3 12 *.c
query /e 5 6 *.gif
query /e 6 1 *.c

Output Sample #2

7
0
4
3
3
1
0

Notes/Hints

Sample One Explanation:

The diagram shows the structure of Sample One, with orange boxes representing folders, grey text indicating file suffixes, and red lines indicating mutual access relationships.

For the first operation: There are 3 txt files between folders 1 and 5, so output 3.
For the second operation: The distance between folders 1 and 4 is 2.
For the third operation: 2 txt files are deleted from folder 2, so output 2.
For the fourth operation: Since the txt files in folder 2 were deleted, there is only 1 txt file between folders 1 and 5.
For the fifth operation: There are 2 vbs files between folders 3 and 4, so output 2.

Data Range:

30% of data satisfies: $n, m <= 100, k <= 3$
50% of data satisfies: $n, m <= 5000, k <= 10$
70% of data satisfies: $n, m <= 2 \times 10^4, k <= 50$
90% of data satisfies: $n, m <= 5 \times 10^4$
100% of data satisfies: $n, m <= 10^5$, total number of files is less than $5 \times 10^5$, file suffixes are lowercase strings not exceeding 6 characters.

Additional Notes:

1. About 50% of the data is generated completely randomly.
2. Weakened version of the data: PION Suffix Automaton (Weakened Version)

见题面 Input 部分

见题面 Output 部分