Control Point

Time limit5sMemory limit512 MB

Summary

Count the subsets of tree vertices where every special vertex has a chosen control point within r edges, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Combinatorics
Solved: No attempts yet

Statement

Bobo has a tree with $n$ vertices. There are $m$ vertices on the tree that Bobo considers special.

Bobo wants to choose a subset of vertices (possibly empty) as control points, so that every special vertex can reach a control point using no more than $r$ edges.

Count the number of such subsets, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
3 1 1
1
1 2
2 3
```
Expected output
```
6
```
Example 2
Input
```
4 1 2
1
1 2
2 3
2 4
```
Expected output
```
15
```