TopCoder Statistics - Problem Statement

Problem Statement

You are given an undirected tree on N nodes, numbered from 0 to N-1. Each node x has some value V[x]. Below we define how to compute the cost of rooting the tree at some node r. Your task is to find the root for which that cost is minimized and to return that minimal cost.

When we root the tree at the node r, each node x will require some payment C[r,x]. The cost of rooting the tree at r is the sum of C[r,x] over all x. The value C[r,x] is defined as follows:

Let the nodes on the (unique) simple path from the root r to x be the nodes r = s₀, s₁, s₂, ..., s_k = x. Then, C[r,x] = V[s₀] * 0 + V[s₁] * 1 + ... + V[s_k] * k.

You are given the int N, the int[]s edge and val, and the ints D, seed, and MX. Use the pseudocode below to generate the edges of the tree and the values of all its nodes.

A[0] = seed
for i = 1 to 2*N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

E = edge
for i = size(edge) to N-1:
    E[i] = (A[i] modulo min(i,D)) + i - min(i,D) 

for i = 1 to N-1:
    the tree contains an edge between i and E[i]

V = val
for i = size(val) to N-1:
    V[i] = A[N+i] modulo MX

Definition

Class:: RootItRight
Method:: findMinimumTotalCost
Parameters:: int, int[], int[], int, int, int
Returns:: long
Method signature:: long findMinimumTotalCost(int N, int[] edge, int[] val, int D, int seed, int MX)
(be sure your method is public)

Notes

Be careful to avoid potential overflows.
The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

N will be between 1 and 200,000, inclusive.
The number of elements in edge will between 1 and min(N, 100), inclusive.
edge[0] will be equal to -1.
For i > 0, edge[i] will be between 0 and i-1, inclusive.
The number of elements in val will between 0 and min(N, 100), inclusive.
Each element of val will be between 0 and MX-1, inclusive.
D will be between 1 and 200,000, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.
MX will be between 1 and 1,000, inclusive.

Examples

2

{-1}

{}

114575

304655178

1000

Returns: 688
5

{-1}

{}

48772

383616353

1000

Returns: 2300
7

{-1}

{}

190629

682098057

1000

Returns: 3866
2

{-1}

{}

7775

685975157

1000

Returns: 376
22

{-1}

{}

4784

1269929825

1000

Returns: 62245
36

{-1}

{}

31932

467588830

1000

Returns: 90902
8

{-1}

{}

78537

618002001

1000

Returns: 13635
19

{-1}

{}

86918

1083678843

1000

Returns: 31705
39

{-1}

{}

38506

652839596

1000

Returns: 124011
8

{-1}

{}

161868

1891466096

1000

Returns: 7106
20

{-1}

{}

96263

1674724049

1000

Returns: 27469
9

{-1}

{}

36991

835051398

1000

Returns: 6402
35

{-1}

{}

177068

253751719

1000

Returns: 101664
20

{-1}

{}

91757

56514242

1000

Returns: 33539
14

{-1}

{}

194328

1536994396

1000

Returns: 23667
35

{-1}

{}

196221

748244296

1000

Returns: 64957
2

{-1}

{}

131545

1362590559

1000

Returns: 602
27

{-1}

{}

175467

42244722

1000

Returns: 47758
11

{-1}

{}

6504

1172109979

1000

Returns: 14553
34

{-1}

{}

144965

1484816172

1000

Returns: 77310
196565

{-1}

{}

45895

775865589

1000

Returns: 10179645419
195554

{-1}

{}

108325

1940985235

1000

Returns: 6797043432
180337

{-1}

{}

48153

1047774984

1000

Returns: 6402724346
181785

{-1}

{}

197489

1485008335

1000

Returns: 7054032439
193296

{-1}

{}

166466

620811552

1000

Returns: 3585360933
193474

{-1}

{}

53968

951768109

1000

Returns: 9206971362
195290

{-1}

{}

33792

1081745524

1000

Returns: 9755855159
183579

{-1}

{}

179694

1125252224

1000

Returns: 3046562523
182001

{-1}

{}

24712

1472948137

1000

Returns: 12616080302
194105

{-1}

{}

102643

1886326457

1000

Returns: 7530711804
193144

{-1}

{}

123492

1116601988

1000

Returns: 5829850834
181972

{-1}

{}

28607

2000212165

1000

Returns: 11621549893
195723

{-1}

{}

160717

1491667182

1000

Returns: 7159155030
196115

{-1}

{}

106986

1489398184

1000

Returns: 5921849131
180071

{-1}

{}

23620

344556846

1000

Returns: 12216649577
193819

{-1}

{}

76858

275413463

1000

Returns: 8119388370
180392

{-1}

{}

88502

1166868834

1000

Returns: 6290590335
197026

{-1}

{}

172325

209552603

1000

Returns: 7341910131
195423

{-1}

{}

120464

973281343

1000

Returns: 7118326804
180422

{-1}

{}

29832

155904035

1000

Returns: 12065477841
195083

{-1}

{}

178720

1815023882

1000

Returns: 5700342435
189577

{-1}

{}

189992

555670314

1000

Returns: 5931669811
191439

{-1}

{}

98989

1312046806

1000

Returns: 6685509676
193189

{-1}

{}

146600

1697330378

1000

Returns: 6602898115
180080

{-1}

{}

11929

1217723135

1000

Returns: 28359538906
181413

{-1}

{}

189770

1305211359

1000

Returns: 7400312139
180665

{-1}

{}

104628

119887591

1000

Returns: 6802258369
180896

{-1}

{}

81898

1998829856

1000

Returns: 3923557400
195281

{-1}

{}

115811

1695015153

1000

Returns: 7348666463
186772

{-1}

{}

3384

1582553146

1000

Returns: 210130390175
186277

{-1}

{}

80114

792467643

1000

Returns: 8166918422
199469

{-1}

{}

89334

351958574

1000

Returns: 7578260927
184194

{-1}

{}

78326

762539680

1000

Returns: 4253145266
191667

{-1}

{}

70962

1231353581

1000

Returns: 7681632328
193222

{-1}

{}

48231

1703602797

1000

Returns: 10354819752
198819

{-1}

{}

171588

860081201

1000

Returns: 7555626240
197449

{-1}

{}

157564

1986844002

1000

Returns: 5636665414
192591

{-1}

{}

68747

1273507743

1000

Returns: 8401485167
195222

{-1}

{}

147593

645858157

1000

Returns: 7296737939
187272

{-1}

{}

12516

258703899

1000

Returns: 29711079418
189394

{-1}

{}

69525

1734317987

1000

Returns: 8275839092
197263

{-1}

{}

157163

1859341419

1000

Returns: 7647013737
193235

{-1}

{}

158976

130768895

1000

Returns: 6947146667
190070

{-1}

{}

193590

731127055

1000

Returns: 7054912850
191482

{-1}

{}

83220

475931742

1000

Returns: 6405802058
182878

{-1}

{}

84239

1476444000

1000

Returns: 4169460498
190976

{-1}

{}

122601

867075258

1000

Returns: 6765791652
196168

{-1}

{}

43377

2004518888

1000

Returns: 7140255504
192183

{-1}

{}

138238

827605671

1000

Returns: 6957222105
195124

{-1}

{}

171653

970633729

1000

Returns: 6746600645
197438

{-1}

{}

111957

150016523

1000

Returns: 7617768716
196396

{-1}

{}

126878

281807537

1000

Returns: 6813781090
196203

{-1}

{}

1999

2107198754

1000

Returns: 680703885672
199060

{-1}

{}

171826

552035524

1000

Returns: 6668179294
196648

{-1}

{}

51401

1446717362

1000

Returns: 8886011064
186621

{-1}

{}

76763

211587627

1000

Returns: 8046223539
181840

{-1}

{}

181495

337657227

1000

Returns: 6412925406
187707

{-1}

{}

80206

1099226773

1000

Returns: 7669114749
193117

{-1}

{}

53310

1889441858

1000

Returns: 8041710288
190685

{-1}

{}

147611

988497740

1000

Returns: 5471935591
192260

{-1}

{}

193559

566462510

1000

Returns: 8695788925
187689

{-1}

{}

158949

1130490963

1000

Returns: 6492903457
186067

{-1}

{}

32737

1718873251

1000

Returns: 10916997578
187271

{-1}

{}

22306

1281586877

1000

Returns: 15636946392
182976

{-1}

{}

105542

6997870

1000

Returns: 6892849899
199648

{-1}

{}

11094

1535275087

1000

Returns: 38910905453
192719

{-1}

{}

10898

1223178129

1000

Returns: 37064797204
198295

{-1}

{}

29964

835176537

1000

Returns: 12890488004
198973

{-1}

{}

40720

1258829633

1000

Returns: 9944806275
199818

{-1}

{}

104917

1356661202

1000

Returns: 6452525674
191669

{-1}

{}

198183

2010757405

1000

Returns: 7269602812
181723

{-1}

{}

153541

1941292723

1000

Returns: 6714408533
183005

{-1}

{}

163316

1806434480

1000

Returns: 5273746567
199101

{-1}

{}

37611

1256184982

1000

Returns: 10306800566
183497

{-1}

{}

2024

81875497

1000

Returns: 537878848278
181834

{-1}

{}

100304

548386447

1000

Returns: 7035305668
181757

{-1}

{}

99876

36394329

1000

Returns: 7262156198
195666

{-1}

{}

53939

74129481

1000

Returns: 8911697779
185565

{-1}

{}

138323

598132718

1000

Returns: 6316011339
184904

{-1}

{}

81154

1184546405

1000

Returns: 7095222557
189159

{-1}

{}

43

521755374

1000

Returns: 298792312158415
188800

{-1}

{}

100

823025680

1000

Returns: 55100229175086
185696

{-1}

{}

79

920508279

1000

Returns: 86682019863266
182773

{-1}

{}

14

1008688611

1000

Returns: 1992185909674056
190820

{-1}

{}

100

605021878

1000

Returns: 55849218256919
185716

{-1}

{}

20

228033024

1000

Returns: 930221386003179
195789

{-1}

{}

74

1518999845

1000

Returns: 112478204874210
189177

{-1}

{}

30

1167734122

1000

Returns: 552566543199076
191212

{-1}

{}

46

663095561

1000

Returns: 254829503304043
195152

{-1}

{}

53

943779493

1000

Returns: 217949257036026
185205

{-1}

{}

53

1432859692

1000

Returns: 183924535388457
189978

{-1}

{}

94

1619729806

1000

Returns: 63872822029882
181970

{-1}

{}

75

2142398679

1000

Returns: 90331916701473
186975

{-1}

{}

20

135073917

1000

Returns: 949467344238168
191016

{-1}

{}

45

479650322

1000

Returns: 280534770071755
194200

{-1}

{}

6

934317721

1000

Returns: 9608272857630860
196100

{-1}

{}

52

355954463

1000

Returns: 201609780275065
189453

{-1}

{}

53

773661563

1000

Returns: 195101437023720
184034

{-1}

{}

27

233325109

1000

Returns: 660658935518846
181692

{-1}

{}

38

1899845639

1000

Returns: 319857895971132
187657

{-1}

{}

58

1402421882

1000

Returns: 156987255838920
198851

{-1}

{}

95

1997624454

1000

Returns: 76016213530240
199697

{-1}

{}

51

912784708

1000

Returns: 245614089285385
195256

{-1}

{}

9

802596872

1000

Returns: 6208270466297931
188040

{-1}

{}

8

2058195600

1000

Returns: 2153215668355596
180756

{-1}

{}

50

96481530

1000

Returns: 185923862211297
197972

{-1}

{}

22

1678096578

1000

Returns: 1106554257140610
199935

{-1}

{}

81

1044931331

1000

Returns: 101371929075831
187446

{-1}

{}

37

967652255

1000

Returns: 382990267868588
189704

{-1}

{}

26

1540580900

1000

Returns: 708500623196286
189506

{-1}

{}

26

1651989128

1000

Returns: 721528635184881
191102

{-1}

{}

88

1964886800

1000

Returns: 62554031379721
190804

{-1}

{}

21

1499433465

1000

Returns: 1204024887300463
186162

{-1}

{}

31

2014826696

1000

Returns: 523993004862837
185885

{-1}

{}

54

481598530

1000

Returns: 172384609381647
182754

{-1}

{}

50

2022471547

1000

Returns: 195375859107183
197887

{-1}

{}

26

1352910213

1000

Returns: 839489062413115
185529

{-1}

{}

1

1032772765

1000

Returns: 132769109346800190
195180

{-1}

{}

61

1839820528

1000

Returns: 168070728377841
199655

{-1}

{}

76

1952422982

1000

Returns: 105951619861705
199639

{-1}

{}

66

1802235195

1000

Returns: 143246405571926
181945

{-1}

{}

36

965686221

1000

Returns: 308367733986663
180159

{-1}

{}

18

872230501

1000

Returns: 1226983928730258
198988

{-1}

{}

49

2060558757

1000

Returns: 266215225126123
193396

{-1}

{}

50

833993386

1000

Returns: 227245650368435
190761

{-1}

{}

83

981646968

1000

Returns: 84704557613496
189350

{-1}

{}

59

1041016009

1000

Returns: 157804791553645
180950

{-1}

{}

68

578947970

1000

Returns: 99837543067140
186491

{-1}

{}

55

2034058612

1000

Returns: 178270130439358
185129

{-1}

{}

75

2081419824

1000

Returns: 95185214429724
193359

{-1}

{}

21

1551162904

1000

Returns: 1253245187257624
189389

{-1}

{}

16

1861595385

1000

Returns: 556488287329608
185041

{-1}

{}

48

31948495

1000

Returns: 129383178509889
182488

{-1}

{}

91

2025615740

1000

Returns: 61620227994395
187969

{-1}

{}

68

1523370914

1000

Returns: 107278178742265
191447

{-1}

{}

41

1984906203

1000

Returns: 343923545874424
184138

{-1}

{}

17

706903299

1000

Returns: 1622642668416692
188213

{-1}

{}

68

878115671

1000

Returns: 107189532257376
198085

{-1}

{}

21

1198241675

1000

Returns: 1366909239176313
188188

{-1}

{}

66

372123693

1000

Returns: 123947783702223
184440

{-1}

{}

76

767137520

1000

Returns: 83923843176459
186574

{-1}

{}

64

230075056

1000

Returns: 33923605213225
192760

{-1}

{}

70

1415219274

1000

Returns: 114467824325859
187309

{-1}

{}

32

1625398184

1000

Returns: 136356037679386
190491

{-1}

{}

48

2128301960

1000

Returns: 139718511932230
182534

{-1}

{}

89

1503495658

1000

Returns: 67133272601170
187547

{-1}

{}

34

885904429

1000

Returns: 420302683957185
190512

{-1}

{}

90

996027704

1000

Returns: 72194448651957
185293

{-1}

{}

17

508498255

1000

Returns: 1643910403946851
181970

{-1}

{}

37

869031515

1000

Returns: 348259002115142
186178

{-1}

{}

68

734446802

1000

Returns: 105280040479404
197302

{-1}

{}

45

1805878399

1000

Returns: 301516882554202
192188

{-1}

{}

8

1696119264

1000

Returns: 2311707301834038
193102

{-1}

{}

66

378929103

1000

Returns: 138407133952705
183847

{-1}

{}

76

163105453

1000

Returns: 77895924758114
183859

{-1}

{}

79

377518418

1000

Returns: 84914791720093
186947

{-1}

{}

41

1997010281

1000

Returns: 314577059889666
196314

{-1}

{}

29

1686089733

1000

Returns: 718708318183155
194888

{-1}

{}

66

408035462

1000

Returns: 135286234675464
198783

{-1}

{}

14

1659075385

1000

Returns: 2557442515806593
190007

{-1}

{}

87

317811244

1000

Returns: 78016852052545
189486

{-1}

{}

65

582811182

1000

Returns: 132604933175018
188087

{-1}

{}

48

1824857850

1000

Returns: 133346059483906
190061

{-1}

{}

97

673532145

1000

Returns: 64322665229569
183134

{-1}

{}

72

714060798

1000

Returns: 82144433825280
187512

{-1}

{}

11

781509235

1000

Returns: 3786756666281749
180802

{-1}

{}

42

1244684279

1000

Returns: 258011392280573
198400

{-1}

{}

20

872151019

1000

Returns: 1126189211587780
197691

{-1}

{}

39

424292298

1000

Returns: 418131185860348
195907

{-1}

{}

1

989736302

1000

Returns: 156643192550093768
191776

{-1}

{}

77

654553667

1000

Returns: 99282162723823
183483

{-1}

{}

77

1409567692

1000

Returns: 88368667641518
195618

{-1}

{}

72

1985976077

1000

Returns: 100496279843701
181063

{-1}

{}

62

1593919405

1000

Returns: 120524555969780
196470

{-1}

{}

71

159374580

1000

Returns: 124230620208122
180759

{-1}

{}

20

1712283117

1000

Returns: 853382468125897
185301

{-1}

{}

33

1546808153

1000

Returns: 461927737792835
193790

{-1}

{}

10

1890402613

1000

Returns: 4219455469362659
185056

{-1}

{}

24

1219441398

1000

Returns: 508646085443896
189380

{-1}

{}

24

1101173979

1000

Returns: 548429746637530
4

{-1,0,1,2}

{4,3,3,4}

1

0

5

Returns: 18

The tree is a path 0-1-2-3. If we root it at 0 or 3, the cost is 33. If we root it at 1 or 2, the cost is only 18. Thus, the correct return value is 18. When we root the tree at node 1, the payments for the individual nodes are as follows: C[1,0] = 3*0 + 4*1 = 4 C[1,1] = 3*0 = 0 C[1,2] = 3*0 + 3*1 = 3 C[1,3] = 3*0 + 3*1 + 4*2 = 11
4

{-1,0,0,0}

{3,2,3,0}

1

0

4

Returns: 5

This tree is a star with node 0 in the center. Node 0 is also the optimal root. The payments are C[0,0] = 0, C[0,1] = 2, C[0,2] = 3, and C[0,3] = 0, thus the total cost of rooting the tree at node 0 is 0+2+3+0 = 5.
5

{-1,0,0,1,3}

{5,0,3,2,3}

1

0

6

Returns: 20

Again, an optimal root for this tree is node 0. The total cost is the sum of the following payments: C[0,0] = 5*0 = 0 C[0,1] = 5*0 + 0*1 = 0 C[0,2] = 5*0 + 3*1 = 3 C[0,3] = 5*0 + 0*1 + 2*2 = 4 C[0,4] = 5*0 + 0*1 + 2*2 + 3*3 = 13
17

{-1}

{}

7

176

15

Returns: 620
200000

{-1,0,0,0}

{4,7}

1

0

1000

Returns: 166346919874650680
15

{-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

15

0

2

Returns: 14
15

{-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6}

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

15

0

16

Returns: 416
11

{-1,0,1,2,3,4,0,6,7,8,9}

{10,1,1,1,1,1,2,2,2,2,2}

6

0

11

Returns: 105
20000

{-1 }

{ }

20000

265006334

100

Returns: 45781954

Statistics

Problem Statement for "RootItRight"

Problem Statement

Definition

Notes

Constraints

Examples