Fix the Tree
Time limit1sMemory limit1024 MB
Given a tree with some broken vertices, repair at most K of them to maximize the number of vertices that still work, where a vertex works only if no ancestor is broken.
- Level
Medium6 of 10
- Topics
- Tree, Dynamic programming, Sorting
- Solved
- No attempts yet
Problem
A rooted tree with vertices has vertex 1 as its root. Each vertex is numbered with a distinct integer from to . The tree has broken vertices. A broken vertex does not work, and neither do its descendants, whether or not they are broken. In other words, a vertex does not work if at least one of its ancestors is broken.
Repair at most broken vertices to maximize the number of vertices that work.
Input
The first line contains three integers (), (), and (), separated by spaces. is the number of vertices, is the number of broken vertices, and is the maximum number of vertices you can repair.
Each of the next lines contains two distinct vertices and (), separated by a space, that are connected by an edge.
The line after those contains the numbers of the broken vertices, separated by spaces. All numbers are distinct.
Output
Print the maximum number of working vertices you can get by repairing at most broken vertices.