Birdhunt
Birdhunt
Problem Description
Rar the Cat likes catching birds in his own backyard. In his backyard, there is a gigantic tree that can be described as N nodes (excluding the base) and N-1 branches (edges), with node 0 being the base of the tree and other nodes numbered from 1 to N-1 inclusive. Each node (excluding node 0) will have a parent, whereby traversing from the node to its parent will get you closer to the base of the tree (node 0). It is guaranteed that there is only 1 path between any two nodes. An illustration of a possible tree with 8 nodes is as below:
4 5 6 7 (end of branches are also nodes)
\ \ / /
\ \/ / (branches are edges)
\ 2-----3 (intersections are nodes)
\ |
\ |
\|
1 (the parent of 1 is 0)
|
|
|
0 (0 is the root)
Birds obviously likes trees and they tend to make frequent visits to specific portions of the gigantic tree. For simplicity, we shall assume that each bird will visit only one node of the tree (excluding 0) and stay there until it leaves the tree.
On the other hand, Rar the Cat is a juvenile cat that has only recently mastered the art of climbing trees, having previously known how to only climb sofas. However, Rar the Cat is a very smart cat. He has observed that certain branches (edges) of the tree are unsafe for him to climb safely, whereas certain branches of a tree are considered safe. Since the conditions of the branches can vary from day to day (small branches grow to become bigger/branches weakened by weather), branches can turn from safe to unsafe and vice versa. As such, Rar the Cat can only catch birds if there exist a path from the base of the tree, to the location of the bird, consisting of only of branches that are considered safe on that day itself.
Recently, Rar the Cat has stumbled upon his own diary, with his own writing about the tree. His diary has M lines and spans over the last D days, which each line conforming to one of the following formats:
Day X
This denotes the start of the events that happened on Day X. X will be an integer from 1 to D inclusive. Day X will not appear before Day X-1.Land B
This denotes that a bird has visited the gigantic tree and has landed on node B before the start of the day. (Eg: if this was recorded in Day 3, there will be a bird at node B at Day 3) There will be no two birds at the same node at any point in time.
Flew B
This denotes that a bird that was previously at node B has flew away before the start of the day. (Eg: if this was recorded in Day 3, there will be no bird on node B at Day 3)
Safe E
This denotes that the branch spanning from the parent of node E to node E is now safe for Rar the Cat to climb until it is subsequently deemed unsafe. It is guaranteed that 0 < E < N.
Unsafe E
This denotes that the branch spanning from the parent of node E to node E is now unsafe for Rar the Cat to climb until it is subsequently deemed safe. It is guaranteed that 0 < E < N.
Rar the Cat wants to know how the maximum number of birds he would have been able to catch in these D days provided he only has time to catch one bird per day (and each bird can only be caught once). To help you, Rar the Cat has also observed that each bird stays on the tree for a maximum of 10 days before it will fly off and never return to the tree again. Also, there are only up to 500 birds that visited the tree in the span of the D days. It is assumed that all branches are safe on the first day unless otherwise specified in the diary.
Limits
Number of Nodes (N): 2 ≤ N ≤ 100000
Number of Days (D): 1 < D ≤ 500
Number of Lines (M): D ≤ M ≤ 300000
Subtasks
Subtask 1 (25%): N ≤ 1000
Subtask 2 (25%): There will be at most one bird on the tree at any day
Subtask 3 (50%): As per limits
Input
The first line of input will be the number of testcases, TC, where TC ≤ 40. For each testcase:
The first line will consist of 3 integers, N, D, M.
Subsequent N-1 lines will describe the branches of the tree, the ith of this number will be the parent of the ith node.
Subsequent M lines of input will be Rar the Cat's diary, which will appear in one of the 5 formats explained above.
For clarity, there will be a blank line in between testcases.
Output
For each testcase, output a single integer which is the maximum number of birds Rar the Cat would have been able to catch in those D days.
Sample Input
2
8 4 15
0
1
2
1
2
2
3
Day 1
Unsafe 3
Land 7
Land 6
Land 4
Day 2
Unsafe 2
Flew 4
Day 3
Safe 3
Safe 2
Land 5
Unsafe 1
Day 4
Safe 1
8 6 17
0
1
2
1
2
2
3
Day 1
Unsafe 3
Land 7
Land 6
Land 4
Day 2
Unsafe 2
Flew 4
Day 3
Safe 3
Safe 2
Land 5
Unsafe 1
Day 4
Safe 1
Day 5
Day 6
Sample Output
2
4
On the first day, Rar the Cat can catch those birds on node 4 and 6. However he can only catch one of them for this day.
Day 1:
4* 5 6* 7*
\ \ / /
\ \/ /
\ 2xxxxx3
\ |
\ |
\|
1
|
|
|
0
On the second day, Rar the Cat will not be able to catch either birds on node 4 or 6 as the bird at node 4 has flew away while he cannot reach the bird at node 6. He is also unable to catch the bird at node 7.
Day 2:
4 5 6* 7*
\ \ / /
\ \/ /
\ 2xxxxx3
\ x
\ x
\x
1
|
|
|
0
On the third day, Rar the Cat is unable to reach any of the birds at node 5, 6 or 7 as the branch 0->1 is unsafe.
Day 3:
4 5* 6* 7*
\ \ / /
\ \/ /
\ 2-----3
\ |
\ |
\|
1
x
x
x
0
On the last day, Rar the Cat can catch birds at either node 5, 6 or 7 but can only can catch one per day.
Day 4:
4 5* 6* 7*
\ \ / /
\ \/ /
\ 2-----3
\ |
\ |
\|
1
|
|
|
0
The first testcase ends at Day 4 but the second testcase ends at Day 6. This gives Rar the Cat ample time to catch the remaining 2 birds after Day 4, giving a grand total of 4.
However, if Rar the Cat catches the bird at node 6 on the first day, then he will end up with 3 birds caught. This is not the maximum number he can catch.