TopCoder Statistics - Problem Statement

Problem Statement

Please note that this problem has a non-standard time limit: 4 seconds.

Dimas is very fond of trees, he really enjoys solving problems on trees. Recently, his professor Rohit gave him a very difficult task to solve. This is it:

You're given a tree on N vertices. (A tree is an undirected connected graph with no cycles.) Different edges of the tree may have different lengths. Initially, all vertices are white. You now have to process Q queries. There are two types of queries:

type 1: Given a node x, paint it blue.
type 2: Given a node x, compute the sum of all distances between x and a blue node.

You are given the ints N, Q, startSeed, threshold, and maxDist. Use the algorithm given below as pseudocode to generate both the tree and the sequence of queries you should process.

int curValue = startSeed;

int genNextRandom() {
    curValue = (curValue * 1999 + 17) % 1000003;
    return curValue;
}

void generateInput() {
    for (int i = 0; i &lt; N-1; i++) {
        distance[i] = genNextRandom() % maxDist;
	parent[i] = genNextRandom();
        if (parent[i] &lt; threshold) {
            parent[i] = i;
        } else {
            parent[i] = parent[i] % (i + 1);
        }
    }

    for (int i = 0; i &lt; Q; i++) {
        queryType[i] = genNextRandom() % 2 + 1;
        queryNode[i] = genNextRandom() % N;
    }
}

The output of the above pseudocode are four arrays: parent, distance, queryType, and queryNode.

The arrays parent and distance have N-1 elements each. For each valid i, our tree contains an edge between the vertices (i+1) and parent[i]. The length of that edge is distance[i]. Note that parent[i] will always be between 0 and i, inclusive.

The arrays queryType and queryNode have Q elements each. For each valid i, the i-th query (0-based index) you should process has the type queryType[i], and should be applied to the vertex queryNode[i]. The queries must be processed in the given order.

Return the bitwise XOR of the answers to all type 2 queries.

Definition

Class:: TreeColoring
Method:: color
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long color(int N, int Q, int startSeed, int threshold, int maxDist)
(be sure your method is public)

Notes

The intended solution does not rely on any properties of the tree and queries generator provided in the problem statement. It can process 100,000 queries on any tree containing up to 100,000 vertices. It is also able to calculate individual answers to each type 2 query (not just bitwise XOR of all answers).

Constraints

N will be between 2 and 100,000, inclusive.
Q will be between 1 and 100,000, inclusive.
startSeed will be between 0 and 1,000,002, inclusive.
threshold will be between 0 and 1,000,003, inclusive.
maxDist will be between 1 and 1,000,003, inclusive.

Examples

4

6

15

2

5

Returns: 7

parent = {0,1,2} distance = {2,1,3} queryType = {2,1,2,2,2,1} queryNode = {2,3,2,3,1,3} Here are our responses to the 6 queries: There are no blue nodes so the answer is clearly zero. We paint the node #3 blue. The distance between node #2 and node #3 is 3. The distance between node #3 and itself is 0. The distance between node #1 and node #3 is 4. As the node #3 is already blue, we just ignore this query.
4

5

2

9

10

Returns: 30

Here are the edges of the tree you should generate: 0-1 (length 5), 0-3 (length 4), and 1-2 (length 6). For query 0 we return 0 because there are no blue nodes yet. Queries 1 and 2 instruct us to color vertices 0 and 3 blue. Then, query 3 asks us to compute the sum of distances between the vertex 2 and each of the blue nodes. The distance between 2 and 0 is 11, and the distance between 2 and 3 is 15. Hence the sum of all distances is 11+15 = 26. Similarly we can compute that the answer to the last query is 4+0 = 4.
8

8

3

5

7

Returns: 6
14750

50

29750

1157

21610

Returns: 2537640
21757

2156

27143

12487

21037

Returns: 100922593
22021

20630

22965

7480

27859

Returns: 631206129
50000

50000

30255

1

25573

Returns: 333521583
3625

6125

2091

25903

22724

Returns: 509897750
24248

2419

10292

26481

73

Returns: 1508409
32372

17385

17471

17759

16526

Returns: 1771554676
13474

27879

29791

2

17874

Returns: 1468661284
5967

13382

28693

27630

15616

Returns: 787571963
50000

50000

156

1000003

4942

Returns: 711257671079
10026

19407

10705

365

3562

Returns: 99858063
14572

18441

30420

2

8002

Returns: 533356512
12035

24255

26961

21433

32574

Returns: 2287019045
11757

2325

10310

19393

12011

Returns: 63205429
2716

22244

15540

15359

15289

Returns: 138547051
50000

50000

15255

2

27011

Returns: 3373518012
16073

8541

23044

18501

22612

Returns: 896876681
19649

17297

3781

1797

10481

Returns: 892866137
18220

5893

22595

9229

7451

Returns: 60843285
313

31836

22762

2

1934

Returns: 1518673
19262

29426

26576

22833

28982

Returns: 1839815362
50000

50000

3151

1000003

10907

Returns: 1498546911529
6522

15333

5277

7439

27640

Returns: 2048030238
4421

22367

12625

1

8553

Returns: 457976131
7709

2687

2313

25616

3276

Returns: 34521326
21639

1671

29642

14013

14826

Returns: 98406028
10202

24115

7368

27946

25

Returns: 2079799
50000

50000

10835

2

27482

Returns: 7343365547
23264

5854

32080

2260

16294

Returns: 332436981
26922

3899

6076

14833

24134

Returns: 692339000
27335

22451

29141

26778

9005

Returns: 1234412162
16869

22397

6070

1

25533

Returns: 2181842945
27727

28558

20138

4731

12862

Returns: 2616624752
50000

50000

14446

19795

23975

Returns: 6124134243
23156

28688

17390

18967

26413

Returns: 1278688228
32727

13777

30246

1

5769

Returns: 453694387
4506

19172

5728

10777

7116

Returns: 109118149
24816

7905

26269

17135

20459

Returns: 962627669
19405

32606

24153

24048

26574

Returns: 1020456238
100000

100000

123456

1000003

1000003

Returns: 319709385188692
100000

100000

123456

500000

474747

Returns: 726915029831
100000

100000

654321

1000003

1000003

Returns: 562600687570528
2

100000

492142

947

159

Returns: 0
14929

99619

354132

0

13

Returns: 3864970
99996

76195

614566

197

997590

Returns: 219797167363
99999

99061

713758

999958

999987

Returns: 121483093836767
87544

99627

779593

998490

999489

Returns: 72115633183036
40563

25492

9601

999980

4

Returns: 229744429
37854

99993

97993

14

999946

Returns: 181527590060
2

99923

284937

951

46567

Returns: 0
3

1

923222

0

1000002

Returns: 0
99999

99999

948616

1

7

Returns: 1111722
2

42159

579916

3478

205

Returns: 0
3

99588

955436

151485

3

Returns: 3
99657

240

301196

207

1

Returns: 0
99632

99992

514106

133

999995

Returns: 804955913981
99621

2

165092

991750

905822

Returns: 0
1642

2435

503676

999141

999711

Returns: 157457239805
99997

1643

919209

4

999116

Returns: 8966634853
99997

25331

189310

999886

996457

Returns: 104123166037588
99671

99785

650578

1

64192

Returns: 20069440341
6242

2

922683

13006

996831

Returns: 7647109
44957

99836

932121

448465

993805

Returns: 962822313141
191

10367

730708

810558

111716

Returns: 145452320
209

218

50526

529

1

Returns: 0
99791

468

389679

990394

995393

Returns: 156074689354
2

679

925558

997165

239873

Returns: 184909
916

30

10432

999746

23569

Returns: 63622573
100000

51057

109211

31872

611

Returns: 194379308
6

100000

948340

907978

1000002

Returns: 7810743
656

100000

435252

999997

93

Returns: 14168827
99999

48

443151

357381

1000003

Returns: 74520473
52538

5907

322191

994383

999990

Returns: 2530199020548
99155

55191

397639

986966

1415

Returns: 18393932225
587

1314

137017

982459

372541

Returns: 3846175056
62273

29

676140

0

105

Returns: 9090
2

1

44799

958434

1

Returns: 0
925

99999

38502

1000003

113883

Returns: 11050074858
99885

99488

636795

999961

1

Returns: 0
98283

89640

836754

1293

11279

Returns: 8292583581
99988

97247

873422

1000003

955985

Returns: 837761621290133
92062

21756

711226

91

1

Returns: 0
45244

37

580853

1

996562

Returns: 249758820
100000

29

756704

937110

999534

Returns: 3665129935
100000

31627

650862

7395

1000002

Returns: 202550746800
638

99967

145282

3

999290

Returns: 3357767159
87829

99990

770189

538

999988

Returns: 75060951850
93630

100000

276677

996075

1000001

Returns: 32212261642821
2

15761

924661

997259

195

Returns: 57
2365

99912

946946

999764

971186

Returns: 700526894216
1606

98511

584661

476311

33

Returns: 332681
99982

79494

497043

1

1018

Returns: 824811493
100000

100000

529069

4811

1000003

Returns: 334665678791
100000

100000

739484

957951

1000003

Returns: 8189078024204
100000

100000

597612

47850

1000003

Returns: 829069369262
100000

100000

800981

931759

1000003

Returns: 6736543323738
100000

100000

417341

10

1000003

Returns: 628597310236
100000

100000

114659

21609

1000003

Returns: 443155626631
100000

100000

122047

25

1000003

Returns: 14042447705
100000

100000

70259

758377

1000003

Returns: 4066104231669
100000

100000

57651

243

1000003

Returns: 721680890364
100000

100000

213352

0

1000003

Returns: 1056742168554
100000

100000

54832

998765

1000003

Returns: 224872588037433
100000

100000

438918

996984

1000003

Returns: 23732402458724
100000

100000

241473

23170

1000003

Returns: 39032317964
100000

100000

637803

4

1000003

Returns: 749085821621
100000

100000

247000

168

1000003

Returns: 648824102233
100000

100000

428383

612684

1000003

Returns: 1159520004132
100000

100000

236013

19326

1000003

Returns: 143036450015
100000

100000

141801

999992

1000003

Returns: 903408816646376
100000

100000

699013

1

1000003

Returns: 646334630760
100000

100000

736198

956571

1000003

Returns: 10292837353129
100000

100000

946604

188

1000003

Returns: 1093252120865
100000

100000

398366

890859

1000003

Returns: 5211859914485
100000

100000

299417

64

1000003

Returns: 988575271471
100000

100000

701650

95448

1000003

Returns: 705233151038
100000

100000

451171

3

1000003

Returns: 1009948164500
100000

100000

299883

88489

1000003

Returns: 299276545707
100000

100000

589253

999976

1000003

Returns: 91999497085522
100000

100000

210057

62001

1000003

Returns: 221225429161
100000

100000

509739

15710

1000003

Returns: 94989032238
100000

100000

748929

999991

1000003

Returns: 891359397715247
100000

100000

843093

1000002

1000003

Returns: 482531586333276
100000

100000

831523

4537

1000003

Returns: 689802490136
100000

100000

181840

3856

1000003

Returns: 519828866579
100000

100000

189200

975454

1000003

Returns: 14559354157815
100000

100000

408637

1213

1000003

Returns: 483045086392
100000

100000

722997

163594

1000003

Returns: 999865634957
100000

100000

267579

293

1000003

Returns: 99507069802
100000

100000

515095

740550

1000003

Returns: 2735430413123
100000

100000

862504

16

1000003

Returns: 187747938967
100000

100000

164157

998372

1000003

Returns: 91722541774593
100000

100000

902203

266

1000003

Returns: 313051515278
100000

100000

511455

999957

1000003

Returns: 564750349382874
100000

100000

506668

789410

1000003

Returns: 1332517531412
100000

100000

663071

980023

1000003

Returns: 20276885281772
100000

100000

299070

6440

1000003

Returns: 134821772290
100000

100000

613451

991826

1000003

Returns: 2575846903563
100000

100000

999529

154

1000003

Returns: 612963452072
100000

100000

932471

873450

1000003

Returns: 1426445250824
100000

100000

610916

859

1000003

Returns: 509251743445
100000

100000

222262

252

1000003

Returns: 312255500045
59873

15987

5654

15995

15987

Returns: 344288407
100000

100000

42

765432

654321

Returns: 416571824006
100000

100000

654321

12323

1000003

Returns: 11004493381
100000

100000

123456

100003

1000003

Returns: 525945949094
100000

100000

1

1000003

100000

Returns: 13951251785099
100000

100000

123457

500000

474747

Returns: 213999216176
99999

99999

99999

99999

99999

Returns: 733079405

Statistics

Problem Statement for "TreeColoring"

Problem Statement

Definition

Notes

Constraints

Examples