Problem Background

Is my archery not precise?
——doby

Problem Description

Doby is an archer who loves handling arrows.

One day, he arrives at an archery range and finds that the owner has set up $n$ targets (numbered from $1$ to $n$). There are $n-1$ lines drawn between these targets, forming a tree structure with root $1$. Each target has a score associated with it.

To challenge himself, he chooses a point (called the parent node) and shoots at each target in its subtree (including itself) once, with a $50\%$ probability of hitting each target. The total score he gains after shooting a subtree is the product of the scores of all the targets he hits.

Now, he wants to know the expected total score for choosing different points as the parent node. Since the total score can be very large, you need to output the result modulo $19260817$ (a prime number).

Input Format

The input consists of two positive integers, the total number of targets $n$ and the number of queries $m$.

The next line contains $n$ positive integers, representing the scores of the targets numbered from $1$ to $n$.

The following $n-1$ lines each contain two integers $u$ and $v$, describing an undirected edge in the tree.

The next $m$ lines each contain a positive integer $x$ ($1 \leq x \leq n$), representing a query for the expected total score when choosing target $x$ as the parent node.

Output Format

Output a single positive integer $out$.

To reduce the output, define $out$ as the sum of the expected total scores for all queries. Since this involves expected values, you need to compute $\frac{a}{b}$ as $a * b^{-1} \mod (19260817)$. You need to output $out$ modulo $19260817$.

Sample Input and Output

Sample Input #1

2 1
1 2
2 1
1

Sample Output #1

14445614

Sample Input #2

5 3
4 4 3 4 5
1 2
3 2
2 4
5 4
3
2
1

Sample Output #2

16251447

Notes

Note: Due to the large modulus, be cautious of overflow in intermediate results when computing the inverse.

If you do not need to optimize for time, using fast exponentiation to find the inverse is sufficient.

Sample #1 Explanation

The answer is $\frac{5}{4}$, with possible total scores being $0$, $1$, and $2$.

Sample #2 Explanation

The answers are $9630410$, $10834247$, and $15047607$, which correspond to $\frac{3}{2}$, $\frac{599}{16}$, and $\frac{2999}{32}$.

Subtask #1 (10 points):

$1 \leq n, m \leq 10$.

Subtask #2 (40 points):

$1 \leq n, m \leq 100000$.

Subtask #3 (50 points):

$1 \leq n, m \leq 2000000$.

All test cases have a time limit of $1.5$ seconds and a memory limit of $125$ MB.

Problem Author: 1jia1

见题面 Input 部分

见题面 Output 部分