1. Homepage
2. Programming
3. CSC3100 Data Structures Fall 2023 Programming Assignment 3: Node Distance, Price Sequence

# CSC3100 Data Structures Fall 2023 Programming Assignment 3: Node Distance, Price Sequence

CUHKCSC3100Data StructuresNode DistancePrice SequenceC++JavaPython

CSC3100 Data Structures Fall 2023 Programming Assignment 3

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:

|B|−1 |B|
Ans= XX dist(bi,bj)

i=1 j =i+1
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, . . . , ln1}, 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 Sample Output 1

This sample considers a tree with 5 nodes:

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 Sample Output 2

9 96 010111111
12
13

22 21 52 53 12 71

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.

For100%ofthetestcases,1n105,1qp1 <p,1wp 1000

Test Case No. 1-4

5-7 8
9 10

Hint

Constraints n 100
n 1000 qp = p

qp = 1

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.

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 , ..., an1 } of length n (n 100000). Please help him to manage this price sequence. There are three types of operations:

CLOSEST PRICE: output the absolute difference between the two closest prices in the entire se- quence.

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

34

Sample Input 2

6 12
30 50 39 25 12 19 BUY 4 CLOSEST_PRICE

Sample Output 1

6 1 6

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

For 100% of the test cases, 2 n, m 1 × 105, 0 ai, x 1012

Test Case No. 1-4

5-6 7-9 10

Hint

Constraints
n 103,m 103
There is no CLOSEST PRICE operation
ai and x are uniformly distributed at random within the range [0,1012] No additional constraints

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.

## Get in Touch with Our Experts

QQ
WeChat
Whatsapp
CUHK代写,CSC3100代写,Data Structures代写,Node Distance代写,Price Sequence代写,C++代写,Java代写,Python代写,CUHK代编,CSC3100代编,Data Structures代编,Node Distance代编,Price Sequence代编,C++代编,Java代编,Python代编,CUHK代考,CSC3100代考,Data Structures代考,Node Distance代考,Price Sequence代考,C++代考,Java代考,Python代考,CUHKhelp,CSC3100help,Data Structureshelp,Node Distancehelp,Price Sequencehelp,C++help,Javahelp,Pythonhelp,CUHK作业代写,CSC3100作业代写,Data Structures作业代写,Node Distance作业代写,Price Sequence作业代写,C++作业代写,Java作业代写,Python作业代写,CUHK编程代写,CSC3100编程代写,Data Structures编程代写,Node Distance编程代写,Price Sequence编程代写,C++编程代写,Java编程代写,Python编程代写,CUHKprogramming help,CSC3100programming help,Data Structuresprogramming help,Node Distanceprogramming help,Price Sequenceprogramming help,C++programming help,Javaprogramming help,Pythonprogramming help,CUHKassignment help,CSC3100assignment help,Data Structuresassignment help,Node Distanceassignment help,Price Sequenceassignment help,C++assignment help,Javaassignment help,Pythonassignment help,CUHKsolution,CSC3100solution,Data Structuressolution,Node Distancesolution,Price Sequencesolution,C++solution,Javasolution,Pythonsolution,