Neko and tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 33 Accepted Submission(s): 7
Problem Description
Neko has a tree with $n$ nodes.
There are $m$ key nodes on tree. Neko want to you to selecte some key nodes satisfying the distance between any two selected nodes less than or equal to $k$.
Neko thinks this work is too easy,so Neko want to know how many different way for selecting nodes.
Calculate the answer after mod $10^9+7$.
Note that you have to select at least one key node.
There are $m$ key nodes on tree. Neko want to you to selecte some key nodes satisfying the distance between any two selected nodes less than or equal to $k$.
Neko thinks this work is too easy,so Neko want to know how many different way for selecting nodes.
Calculate the answer after mod $10^9+7$.
Note that you have to select at least one key node.
Input
The first line contains three integers $n, m, k(1 \leq n,m,k \leq 5000)$.
The next $n-1$ line, each line contains two integers $u, v$,indicating there is an edge connecting node $u$ and node $v$.
The last line contains $m$ integers, indicating key node.
The next $n-1$ line, each line contains two integers $u, v$,indicating there is an edge connecting node $u$ and node $v$.
The last line contains $m$ integers, indicating key node.
Output
Output the number of way for selecting nodes.
Sample Input
4 3 2 1 2 1 3 2 4 2 3 1
Sample Output
7