Caterpillars | Topcoder Archive

Problem Statement

A tree caterpillar, as the name suggests, is a tree, in which each vertex is either black or white. The black vertices form the body of the caterpillar. They must all form a single simple path. White vertices are called legs of the caterpillar. Each white vertex must be a leaf of the tree and it must be adjacent to a black vertex. Additionally, one end of the body is called the head of the caterpillar and the other end is called its tail. (If the body consists of a single vertex, its head and tail coincide. Some legs may be attached to the head and/or to the tail of the caterpillar.)

There's a group of N young caterpillars, each consisting of a single black vertex. These vertices are numbered 0 through N-1. Each of them currently forms the entire body of one caterpillar. The caterpillars are hungry and there are only two food sources: they can eat either leaves or other caterpillars.

You should process Q queries, which are described by int[]s type, U and V. In query i, one of the following events happens:

If type[i]=0, the caterpillar that contains vertex U[i] eats a leaf and grows a new leg. This new leg will have no number. It will be attached to vertex U[i] by an edge.
If, for type[i]=1, vertices U[i] and V[i] already belong to the same caterpillar, that caterpillar is chasing its own tail - ignore this query.
If type[i]=1 and vertices U[i] and V[i] belong to two different caterpillars C_u and C_v, caterpillar C_u eats the caterpillar C_v. Formally, it means that the two caterpillars are merged into one - an edge is added between the tail of caterpillar C_u and the head of caterpillar C_v. The head of the resulting caterpillar will be the former head of C_u and its tail will be the former tail of C_v.

The answers to all ignored queries are 0. If there's a path between vertices u and v, their distance is the number of edges on that path; otherwise, their distance is 0. The answer to a non-ignored query is the sum of distances between all pairs of vertices after processing this query ("all pairs of vertices" includes pairs in which one or both vertices are legs). Compute and return the bitwise XOR of answers to all queries.

You're given ints N, Q, genA, genK and seed. Use the pseudocode below to generate int[]s type, U and V.

int[] type(Q)
int[] U(Q)
int[] V(Q)

int curValue

int nextRand(): 
	curValue = (genA * curValue + genK) modulo 1234567
	return curValue

generate():
	curValue = seed

	for i = 0 to Q-1:
		type[i] = nextRand() modulo 2
		U[i] = nextRand() modulo N
		V[i] = nextRand() modulo N

In order to generate the input, you should call generate().

Definition

Class:: Caterpillars
Method:: answerQueries
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long answerQueries(int N, int Q, int genA, int genK, int seed)
(be sure your method is public)

Notes

The intended solution doesn't depend on any properties of the pseudorandom number generator; it should work within the given time limit for any sequence of queries. It's also able to separately compute the answers to all individual queries (not just their XOR).

Constraints

N will be between 1 and 100,000, inclusive.
Q will be between 1 and 300,000, inclusive.
genA and genK will be between 0 and 1,000, inclusive.
seed will be between 0 and 1,000,000, inclusive.

Examples

```
5
```
```
6
```
```
67
```
```
111
```
```
42
```
```
Returns: 0
```
The values of type[i],U[i],V[i] and answers to queries are: type[0]=1, U[0]=1, V[0]=3, answer: 1; type[1]=0, U[1]=0, V[1]=1, answer: 2; type[2]=0, U[2]=0, V[2]=4, answer: 5; type[3]=1, U[3]=3, V[3]=4, answer: 8; type[4]=1, U[4]=4, V[4]=0, answer: 32; type[5]=1, U[5]=4, V[5]=2, answer: 46. A sketch of caterpillars after each query (arrows point from tail to head):
```
6
```
```
10
```
```
789
```
```
310
```
```
701928
```
```
Returns: 81
```
The answers to individual queries are 1,2,5,6,0,9,15,51,0,100.
```
20
```
```
6
```
```
8
```
```
9
```
```
0
```
```
Returns: 0
```
The answers to inidividual queries are 1,4,5,6,9,15.
```
20
```
```
200
```
```
17
```
```
1
```
```
5
```
```
Returns: 27965
```
```
50000
```
```
50000
```
```
2
```
```
383
```
```
1000000
```
```
Returns: 706096
```

Returns: 52774483

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.