Flashing Lights
YOU: "How do you feel about how the night went?"
JAMIE: "Oh, it was the worst! I had this amazing setlist planned, right? Just total peak. Then Kevin tells me it all needs to change. Says my taste is 'too niche' for the crowd. They just don't know ball! They have zero ball knowledge, and now that's my problem?"
YOU: "How long did it take you to come up with a new setlist?"
JAMIE: "All afternoon! Do you know what it's like deconstructing something like a setlist? It's violence. Cultural violence."
YOU: "So you were stuck at your DJ booth all afternoon?"
JAMIE: "Pretty much. It was just a rush of tuning, rebuilding, tuning, and rebuilding. I was a bit scared I wouldn't get everything done in time! Gleb dropped a crate off at some point. Rory came by too, I think he said something to me? Honestly, I had headphones on. He kind of hovered and left."
Jamie is preparing a light show to accompany his DJ set at the ACPC ball. The show uses LEDs connected by wires in the shape of a rooted tree. LED
is connected to the wall and is the root. Every other LED has exactly one parent LED.
Before the show, Jamie has noticed that of the LEDs are broken and need to be checked by maintenance. To call maintenance, Jamie selects some simple path from the root of the tree to one of its leaves. Then, maintenance will check every LED on this path including both endpoints.
Jamie can call maintenance multiple times, making them check LEDs on multiple different paths through the tree. However, he wants to bother maintenance as little as possible. What is the minimum number of paths Jamie he needs to select, to ensure all broken LEDs are checked at least once?
Input
The first line contains two integers and
(
), the number of LEDs in the tree, and the number of broken LEDs. The LEDs are labeled
through to
with
being the root.
The next line contains space-separated integers
(
,
), the parent of each LED. Notice that LED
has no parent, so the first integer here is the parent of LED
. This is guaranteed to form a valid rooted tree with root
.
The next line contains space-separated integers
(
). Each integer represents the label of a broken LED. The integers in this line are guaranteed to be unique and strictly increasing.
Output
Output a single integer, the minimum number of paths that Jamie must select for maintenance to check, so that all broken LEDs are checked.
Example
Input 1
5 2
1 1 2 2
2 4
Output 1
1
The tree looks as follows:
1
/ \
2* 3
/ \
4* 5
If Jamie selects tbe path , both broken LEDs are checked, so one path is enough.
Input 2
6 3
5 5 1 1 4
2 3 4
Output 2
3
The tree looks as follows:
1
/ \
5 4*
/ \ \
2* 3* 6
LEDs ,
and
are broken, but no two lie on the same path from the root. Therefore, Jamie must select three paths to cover all of them:
Comments