5329: Course
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
The new semester has begun, and Bob needs to start selecting courses.There are n courses in school, the credit for the i-th course is si.
Bob can select multiple times in the same course, if he select ki times for the i-th course, his total credits are ∑ i=1 n kisi .
And Bob's training program has some limitations. The training program is a rooted tree of these nn courses, each limitation means the total credits in the subtree of x need to be at least cx.
Now Bob wants to know the number of ways to select courses satisfy the limitations of training program and the total credits are w.
Two ways are different if and only if there exists at least one i∈[1,n] which satisfies that the select times of the i-th courses are different in these two plans.
The answer may be very large, you only need to output the answer module 998244353.
Bob can select multiple times in the same course, if he select ki times for the i-th course, his total credits are ∑ i=1 n kisi .
And Bob's training program has some limitations. The training program is a rooted tree of these nn courses, each limitation means the total credits in the subtree of x need to be at least cx.
Now Bob wants to know the number of ways to select courses satisfy the limitations of training program and the total credits are w.
Two ways are different if and only if there exists at least one i∈[1,n] which satisfies that the select times of the i-th courses are different in these two plans.
The answer may be very large, you only need to output the answer module 998244353.
输入
The first line has two integers n, Q.
Then there are n−1 lines to describe the rooted tree of training program, each line has two integers a,b denote a is the parent node of b.
Next line has n integers s1...n.
Next line has n integers c1...n.
Then there are Q lines, each line has one integers wi denote the total credits of the i-th query.
1≤n≤100，1≤Q≤10，1≤si≤5，0≤ci≤150，1≤a<b≤n，0≤wi≤108
Then there are n−1 lines to describe the rooted tree of training program, each line has two integers a,b denote a is the parent node of b.
Next line has n integers s1...n.
Next line has n integers c1...n.
Then there are Q lines, each line has one integers wi denote the total credits of the i-th query.
1≤n≤100，1≤Q≤10，1≤si≤5，0≤ci≤150，1≤a<b≤n，0≤wi≤108
输出
Output Q lines, each line has one integer denote the answer of the i-th query.
样例输入 复制
3 5
1 2
1 3
1 1 2
6 2 3
10
11
12
13
1000样例输出 复制
9
12
16
20
248004