Codeforces Round 695 (Div. 2)


A. Wizard of Orz
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
1
2
Output
9
98
----------------------------------------------------------------------------------------------------
B. Hills And Valleys
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3
1 5 3
5
2 2 2 2 2
6
1 6 2 5 2 10
5
1 6 2 5 1
Output
0
0
1
0
----------------------------------------------------------------------------------------------------
C. Three Bags
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 4 1
1 2
6 3 4 5
5
Output
20
Input
3 2 2
7 5 4
2 9
7 1
Output
29
----------------------------------------------------------------------------------------------------
D. Sum of Paths
time limit per test: 3 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2
Output
62
58
78
86
86
Input
5 2 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2
Output
157
147
207
227
227
Input
4 40 6
92 21 82 46
3 56
1 72
4 28
1 97
2 49
2 88
Output
239185261
666314041
50729936
516818968
766409450
756910476
----------------------------------------------------------------------------------------------------
E. Distinctive Roots in a Tree
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 5 1 1 4
1 2
1 3
2 4
2 5
Output
3
Input
5
2 1 1 1 4
1 2
1 3
2 4
2 5
Output
0
----------------------------------------------------------------------------------------------------
