F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Neko and tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1053    Accepted Submission(s): 408


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.
 

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.
 

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
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-26 09:19:49, Gzip enabled