Programming Assignment 3 Node Distance

CSC3100 Data Structures 
Programming Assignment 3
Assignment Link: http://oj.cuhk.edu.cn/contest/csc310023falla3
Access Code: 9v7Dxqet
1 Node Distance(40% of this assignment)
1.1 Description
You are given a tree with n nodes, where each edge in the tree has a corresponding weight denoting the
length of each edge. The nodes in the tree are colored either black or white. Your task is to calculate
the sum of distances between every pair of black nodes in the tree. Let B = {b1, b2, ...} a set of black
nodes, then the answer is formulated as:
Ans =
|B
X
|−1
i=1
X
|B|
j=i+1
dist(bi
, bj )
where |B| denotes the number of the black nodes in the tree, and dist(bi
, bj ) is the length of the simple
path from the i-th to j-th black node.
Write a program to calculate the sum of distances on the tree between every pair of black nodes Ans
in the given tree.
1.2 Input
The first line contains an integer n, representing the number of nodes in the tree.
The second line contains n space-separated integers {c1, c2, . . . , ci
, . . . , cn} where ci
is either 0 or 1.
ci = 1 indicates that the i-th node is black, and ci = 0 indicates that the i-th node is white.
The following n − 1 lines, {l1, l2, . . . , lp, . . . , ln−1}, denoting the structure of the tree follow, each line
lp contains 2 integers qp and wp, denoting an edge of length wp between the p + 1-th node and the
qp-th node.
1.3 Output
Output the sum of distances for every pair of black nodes in the tree.
Sample Input 1
5
0 1 1 1 1
1 1
1 2
3 2
3 1
Sample Output 1
18
4
This sample considers a tree with 5 nodes:
1
2 3
4 5
1 2
2 1
The 1-st node is white, and 2-, 3-, 4-, 5-th nodes are black.
The length of edge: (2-nd, 1-st): 1, (3-rd, 1-st): 2, (4-th, 3-rd): 2, (5-th, 3-rd): 1.
Ans = ((1 + 2) + (1 + 2 + 2) + (1 + 2 + 1)) + (2 + 1) + 2 + 1 = 18.
Sample Input 2
9
0 1 0 1 1 1 1 1 1
1 2
1 3
2 2
2 1
5 2
5 3
1 2
7 1
Sample Output 2
96
Three additional large-scale samples are included in the provided files, namely, A samplecase1.in/.ans,
A samplecase2.in/.ans and A samplecase3.in/.ans.
Problem Scale & Subtasks
For 100% of the test cases, 1 ≤ n ≤ 105
, 1 ≤ qp−1 < p, 1 ≤ wp ≤ 1000
Test Case No. Constraints
1-4 n ≤ 100
5-7 n ≤ 1000
8 qp = p
9 qp = 1
10 No additional constraints
Hint
It can be proven that the given structure is definitely an unrooted tree.
For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It
may be too small for this problem. You need other data types, such as long long for C/C++ and long
for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the
input n. And the other operations for long and long long are quite same as int.
For Python users, if there occurs a RecusrionError, see here.
5
2 Price Sequence (50% of this assignment)
2.1 Description
Mario bought n math books and he recorded their prices. The prices are all integers, and the price
sequence is a = {a0, a2, ...ai
, ..., an−1} of length n (n ≤ 100000). Please help him to manage this price
sequence. There are three types of operations:
• BUY x: buy a new book with price x, thus x is added at the end of a.
• CLOSEST ADJ PRICE: output the minimum absolute difference between adjacent prices.
• CLOSEST PRICE: output the absolute difference between the two closest prices in the entire sequence.
A total of m operations are performed (1 ≤ m ≤ 100000). Each operation is one of the three mentioned
types. You need to write a program to perform given operations. For operations ”CLOSEST ADJ PRICE”
and ”CLOSEST PRICE” you need to output the corresponding answers.
2.2 Input
The first line contains two integers n and m, representing the length of the original sequence and the
number of operations.
The second line consists of n integers, representing the initial sequence a.
Following that are m lines, each containing one operation: either BUY x, CLOSEST ADJ PRICE, or
CLOSEST PRICE (without extra spaces or empty lines).
2.3 Output
For each CLOSEST ADJ PRICE and CLOSEST PRICE command, output one line as the answer.
Sample Input 1
3 4
7 1 9
CLOSEST_ADJ_PRICE
BUY 2
CLOSEST_PRICE
CLOSEST_ADJ_PRICE
Sample Output 1
6
1
6
Sample Input 2
6 12
30 50 39 25 12 19
BUY 4
CLOSEST_PRICE
BUY 14
CLOSEST_ADJ_PRICE
CLOSEST_PRICE
BUY 0
CLOSEST_PRICE
BUY 30
BUY 12
CLOSEST_PRICE
BUY 20
CLOSEST_PRICE
Sample Output 2
5
7
2
2
0
0
Two additional large-scale samples are included in the provided files, namely, B samplecase1.in/.ans
and B samplecase2.in/.ans.
6
Problem Scale & Subtasks
For 100% of the test cases, 2 ≤ n, m ≤ 1 × 105
, 0 ≤ ai
, x ≤ 1012
Test Case No. Constraints
1-4 n ≤ 103
, m ≤ 103
5-6 There is no CLOSEST PRICE operation
7-9 ai and x are uniformly distributed at random within the range [0, 1012]
10 No additional constraints
Hint
For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It
may be too small for this problem. You need other data types, such as long long for C/C++ and long
for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the
input n. And the other operations for long and long long are quite same as int.
For Python users, if there occurs a RecusrionError, see here.
7