Red Black Tree
Time limit4sMemory limit512 MB
Count antichains of a rooted tree (no chosen node is an ancestor of another) with exactly k red nodes, for each k from 0 to m, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Tree
- Solved
- No attempts yet
Problem
You are given a rooted tree with nodes, numbered to . The root is node . Exactly of the nodes are red, and the rest are black.
Choose a subset of nodes such that no chosen node is an ancestor of another chosen node. For example, if is the parent of and is the parent of , then at most one of , , and can be in the subset. You want exactly of the chosen nodes to be red.
For each , count the subsets that contain exactly red nodes and satisfy the condition above.
Input
The first line contains two integers and (, ). Each of the next lines contains one integer , the parent of node , then node , and so on. Each of the next lines contains one integer , the number of a red node. No value of repeats.
Output
Print lines. Line contains the number of valid subsets with exactly red nodes, modulo .