Statistics

Problem Statement for "TaroTreeRequests"

Problem Statement

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

Cat Taro has a rooted tree with N nodes. Nodes are numbered from 0 to N-1, inclusive. Node with the index 0 is the root of the tree. Each edge has some positive integer value written on it.

Taro wants to process M queries. Each query consists of two nodes u and v. Queries should be processed in the following way:

  • If u equals v, print -1.
  • Otherwise, if the node v is in the subtree of the node u, print the maximum value written on the edges that belong to the simple path from u to v.
  • Otherwise, remove the edge between u and its parent. Instead, add a new edge (with the same value) that makes u the child of v. (Note that the entire subtree rooted at u is now a part of the subtree rooted at v.) Do not print anything.

Return the sum of all values that were printed during the process.

You are given the ints N and M. You are also given ints startValue, maxValue, and maxHeight. These are used in the following pseudocode that generates the initial tree and the sequence of queries you should process. 

initialize():
    curValue = startValue

genNextRandom():
    curValue = (curValue * 1999 + 17) modulo 1,000,003
    return curValue

generateTree():
    for i=1 to N-1:
        value[i] = genNextRandom() modulo maxValue;
        parent[i] = max( 0, i - 1 - (genNextRandom() modulo maxHeight) );
        in our tree, the parent of vertex i is parent[i]
        the edge between i and parent[i] has the label value[i]

generateQueries():
    for i=0 to M-1:
        queryU[i] = genNextRandom() modulo N
        queryV[i] = genNextRandom() modulo N
	if queryU[i] > queryV[i]:
		swap queryU[i] and queryV[i]
        process the query with u=queryU[i] and v=queryV[i]

To generate the input, call initialize(), then generateTree(), and finally generateQueries().

Definition

Class:
TaroTreeRequests
Method:
getNumber
Parameters:
int, int, int, int, int
Returns:
long
Method signature:
long getNumber(int N, int M, int startValue, int maxValue, int maxHeight)
(be sure your method is public)

Notes

  • The intended solution should work within the given time limit for an arbitrary tree and an arbitrary sequence of queries. It does not depend on any special properties of the pseudorandom generator.

Constraints

  • N will be between 1 and 200,000, inclusive.
  • M will be between 1 and 200,000, inclusive.
  • startValue will be between 0 and 1,000,002, inclusive.
  • maxValue will be between 1 and 1,000,003, inclusive.
  • maxHeight will be between 1 and 1,000,003, inclusive.

Examples

  1. 4

    4

    47

    7

    2

    Returns: 8

    The explanation to the picture below: 0) The initial tree. 1) The first operation, with u = 0, v = 2. The maximum value is 4. 2) The second operation with u = 1, v = 3. The maximum value is 0. 3) The third operation with u = 2, v = 3. The structure of the tree is changed after this operation. 4) The fourth operation with u = 0, v = 2. The maximum value is 4.

  2. 7

    10

    74

    7

    3

    Returns: 40

  3. 10

    4

    103

    100

    2

    Returns: 220

  4. 10000

    10000

    984848

    1000000

    2

    Returns: 6632008328

  5. 100000

    100000

    954711

    1000000

    2

    Returns: 66780062524

  6. 200000

    200000

    7584

    948984

    4

    Returns: 75766570928

  7. 10000

    10000

    87598

    987937

    10000

    Returns: 2062655

  8. 1

    2

    4774

    1000000

    7

    Returns: -2

  9. 10

    20

    857968

    1000000

    7

    Returns: 5296369

  10. 50

    100

    12

    1000

    10

    Returns: 23235

  11. 100

    200

    984198

    100

    1

    Returns: 18491

  12. 500

    1000

    47

    1

    2

    Returns: -1

  13. 1000

    10

    189118

    100000

    50

    Returns: 189523

  14. 2000

    200000

    970120

    1000000

    2

    Returns: 132268155610

  15. 5000

    200000

    747474

    1000000

    3

    Returns: 100313573544

  16. 10000

    200000

    576012

    1000000

    7

    Returns: 49886010031

  17. 10000

    200000

    340012

    1000000

    1

    Returns: 199617390763

  18. 100000

    200000

    587

    10

    10

    Returns: 326273

  19. 100000

    200000

    6857

    1000000

    2

    Returns: 132785538345

  20. 100000

    200000

    2

    1000000

    1

    Returns: 199953962709

  21. 100000

    200000

    689750

    1000000

    1000000

    Returns: 1422121

  22. 100000

    200000

    17

    6857

    2000

    Returns: 2615897

  23. 100000

    200000

    14754

    1000000

    20000

    Returns: 233104145

  24. 200000

    200000

    3

    10

    1

    Returns: 1799955

  25. 200000

    200000

    6975

    1000

    1

    Returns: 199784871

  26. 200000

    200000

    570100

    1000000

    1

    Returns: 199979860029

  27. 200000

    200000

    666535

    1000000

    2

    Returns: 132943883378

  28. 200000

    200000

    4774

    1

    1000

    Returns: -1

  29. 200000

    200000

    69

    100

    2

    Returns: 13189529

  30. 200000

    200000

    69865

    1000003

    3

    Returns: 100091322915

  31. 200000

    200000

    0

    1000000

    3

    Returns: 100359325661

  32. 200000

    200000

    588586

    1000000

    4

    Returns: 80239508718

  33. 200000

    200000

    333230

    1000000

    5

    Returns: 66731492289

  34. 200000

    200000

    99801

    888888

    10

    Returns: 32629937999

  35. 200000

    200000

    17

    100000

    50

    Returns: 802400340

  36. 200000

    200000

    29

    1995

    100

    Returns: 8081175

  37. 200000

    200000

    25824

    1000000

    500

    Returns: 871629835

  38. 200000

    200000

    440132

    1000002

    2000

    Returns: 339008698

  39. 200000

    200000

    379102

    1000000

    5000

    Returns: 182790275

  40. 200000

    200000

    6

    100078

    20000

    Returns: 17136043

  41. 200000

    200000

    880173

    1000000

    100000

    Returns: 13327242

  42. 200000

    200000

    55

    1000000

    200000

    Returns: 2109421

  43. 200000

    200000

    1715

    1000000

    8

    Returns: 44539558848

  44. 200000

    10

    100000

    100000

    2

    Returns: 699932

  45. 199999

    199995

    58

    458488

    1

    Returns: 91684113757

  46. 199999

    199999

    47

    1000000

    2

    Returns: 133269854716

  47. 5

    200000

    671

    1000000

    4

    Returns: 75754093436

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: