问题 1116. -- Dominator Orz Pandas

1116: Dominator Orz Pandas

时间限制:1000 ms 内存限制:128 MB
提交:30 解决:12
[ 提交][ 状态][ 讨论版]

题目描述

Master Jie has a country with N cities and N-1 roads which form a tree and the capital city 1 is considered as the root of the tree.

As the king of the country,Master Jie wants todominate this country .Since he likes Orz pandas well much,so he decidesto sendN Orz pandas to those cities and each city will have one and only oneOrz panda.

Now Master Jie has NOrz pandas numbered 1 to N,and the ithOrz pandas has an ability value i.

In his country, there are M cities is considered "important",and theOrz pandaof an important city must be a "dominator".

We think anOrz pandais adominatorif and only if he has the maximum ability value in his subcities.

His subcities means the cities in the subtree of his city.

Now Master Jie wants to know how many different ways he has to send theOrz pandas so that each important city has adominator.

But he is too busy to manage his country, can you help him ?

输入

There are multiple test cases (no more than 20),please process to EOF.

In each test case,there are two numbers N and M at the first line. (0<=m<=n<=100000)

Then N-1 lines,each line has two numbers u and v,indicates there is an undirected road between city u and city v.

And then M lines,each line has one number x,indicates the city x is important.

(notice that a same x may appear many times)

输出

One number which is the answer of the question (mod by1e9+7)

样例输入

3 3 1 2 1 3 1 2 3 3 2 1 2 1 3 2 3

样例输出

2 6

提示

来源

[ 提交][ 状态][ 讨论版]
Baidu
map