TopCoder Statistics - Problem Statement

Problem Statement

In Absurdistan, there are N towns, numbered 0 through N-1. The towns are all connected by a network of N-1 bidirectional highways. Different highways may have different lengths. Town 0 is the capital. (Formally, the network of highways is a tree, and you may consider 0 to be the root of the tree.)

For each town v, let T(v) be the subtree rooted at v. Formally, T(v) is the subtree formed by all towns w with the following property: you cannot go from town 0 to town w without visiting town v. Note that town v always belongs to T(v). Also note that T(0) is the entire tree.

Joshua Cohen is a merchant. Today, Joshua had a fight with his wife and decided to leave on a business trip to some T(v).

Joshua's business trips always look as follows: At the beginning of the trip, he flies directly to some town b in the chosen subtree and establishes a base in that town. Then, for each other town w in T(v), he uses local transport to travel from town b to town w and back. After visiting each town in T(v) he flies back home. The total cost of the business trip depends on the sum of distances between the base b and all possible towns w. Joshua always chooses the base b that minimizes this sum. Let D(v) be the smallest possible sum of distances for the tree T(v).

You are given the int N: the number of towns. You are also given ints seed, C, and D. These are the parameters for a function that will generate the tree for you. The function (shown below) produces two int[]s: par and L. The meaning of these arrays is: for each i between 0 and N-2, inclusive, there is a highway of length L[i] that connects the towns par[i] and (i+1). The pseudocode of the function follows.

integer cur := seed
for i = 0 to N-2:
	cur := (C*cur+D) mod 10^9
	par[i] := cur mod (i+1)
	cur := (C*cur+D) mod 10^9
	L[i] := cur mod 10^6

For each v from 0 to N-1, inclusive, compute the value D(v), i.e. the smallest possible sum of distances between the base and all other towns in the subtree T(v). Return the bitwise XOR of all the values D(v).

Definition

Class:: TreeSums
Method:: findSums
Parameters:: int, int, int, int
Returns:: long
Method signature:: long findSums(int N, int seed, int C, int D)
(be sure your method is public)

Constraints

N will be between 1 and 300,000, inclusive.
seed, C and D will be between 0 and 1,000,000,000, inclusive.

Examples

10

1

1

1

Returns: 99
5

310305

116946964

141861

Returns: 1039791
6

6985253

86386005

1

Returns: 3440315
392

6982056

117456126

500000

Returns: 628685472
1

10000

100000

1000000

Returns: 0
300000

158526

418612105

184195163

Returns: 348582411304
300000

1

1

1

Returns: 89999999999
251573

798318594

999999999

1

Returns: 653986905946
290000

1

999999999

1

Returns: 289999
299999

1

999999999

1

Returns: 299998
223353

847213877

871284635

361000115

Returns: 1036127307914
230254

803801772

435555615

535428922

Returns: 1656341566848
205163

363269145

932858149

978419685

Returns: 934991795461
260977

574363999

681570670

215903601

Returns: 587265359057
211356

766433502

323858389

507995969

Returns: 631828036112
288669

180486829

775464662

994449784

Returns: 1984428920388
255410

555109073

390518617

24882218

Returns: 991117425818
285946

59991117

600946906

51680519

Returns: 1407492637392
299562

718010926

406913525

696907615

Returns: 907503896672
257257

815857880

22774668

303093177

Returns: 918494397966
6

8

3

13

Returns: 856320

The tree looks as follows: The values of ans(v) are: D(0)=964356, D(1)=964232, D(2)=856204, D(3)=D(4)=D(5)=0. For T(0), the optimal base is town 1. For T(1), the optimal base is also town 1. For each other v, an optimal base for the subtree T(v) is town v. The correct return value is the value (964356 XOR 964232 XOR 856204 XOR 0 XOR 0 XOR 0).
2

10

20

30

Returns: 4630
6

55

1

18

Returns: 22
300000

999999990

999999990

999999991

Returns: 438628640790
300000

999999990

999999993

499999999

Returns: 392643182944
261853

999999990

1

1

Returns: 134553508597830
299998

999999991

500000001

500000001

Returns: 550512979657272
289999

999999995

1

1

Returns: 2010029617000752
278512

999999998

1

1

Returns: 3892173632651360
291652

999999999

1

1

Returns: 3073850666416527
284165

1000000000

1

1

Returns: 142125953002496
291999

999999990

999999990

999999990

Returns: 680405082840
300000

999999990

999999990

1000000000

Returns: 2898000
228174

999999990

999999999

999999990

Returns: 228170718270
253298

999999990

999999991

999999993

Returns: 813552718898
294518

999999990

999999990

999999991

Returns: 55490381221
299998

999999990

999999990

999999997

Returns: 676539407546
300000

499999993

499999999

499999999

Returns: 59806846673
299995

5

500000001

500000009

Returns: 2402926206521016
299997

499999991

500000001

9

Returns: 859628711274935
294939

999999992

500000001

4

Returns: 1495220387751304
300000

500000008

500000001

500000009

Returns: 1661159802
299999

499999998

500000001

500000009

Returns: 529991478472
288888

999999992

500000001

500000005

Returns: 477777618744
263080

999999990

1

9

Returns: 12055256033392
268868

499999991

1

500000007

Returns: 1103340070497879
295269

500000003

1

500000009

Returns: 3989650641535257
27500

999999992

500000001

4

Returns: 2444580674264
299999

499999999

500000001

9

Returns: 184473140156748
1

575

7667

657

Returns: 0
300000

499999991

500000001

9

Returns: 851247715902894

Statistics

Problem Statement for "TreeSums"

Problem Statement

Definition

Constraints

Examples