TaroTreeRequests | Topcoder Archive

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

```
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.
```
7
```
```
10
```
```
74
```
```
7
```
```
3
```
```
Returns: 40
```
```
10
```
```
4
```
```
103
```
```
100
```
```
2
```
```
Returns: 220
```

Returns: 6632008328

Returns: 75766570928

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.