TreeSums | Topcoder Archive

Problem Statement

In Absurdistan, there are N towns, numbered 0 through N-1. The towns are all connected by a network of N-1 bidirectional highways. Different highways may have different lengths. Town 0 is the capital. (Formally, the network of highways is a tree, and you may consider 0 to be the root of the tree.)

For each town v, let T(v) be the subtree rooted at v. Formally, T(v) is the subtree formed by all towns w with the following property: you cannot go from town 0 to town w without visiting town v. Note that town v always belongs to T(v). Also note that T(0) is the entire tree.

Joshua Cohen is a merchant. Today, Joshua had a fight with his wife and decided to leave on a business trip to some T(v).

Joshua's business trips always look as follows: At the beginning of the trip, he flies directly to some town b in the chosen subtree and establishes a base in that town. Then, for each other town w in T(v), he uses local transport to travel from town b to town w and back. After visiting each town in T(v) he flies back home. The total cost of the business trip depends on the sum of distances between the base b and all possible towns w. Joshua always chooses the base b that minimizes this sum. Let D(v) be the smallest possible sum of distances for the tree T(v).

You are given the int N: the number of towns. You are also given ints seed, C, and D. These are the parameters for a function that will generate the tree for you. The function (shown below) produces two int[]s: par and L. The meaning of these arrays is: for each i between 0 and N-2, inclusive, there is a highway of length L[i] that connects the towns par[i] and (i+1). The pseudocode of the function follows.

integer cur := seed
for i = 0 to N-2:
	cur := (C*cur+D) mod 10^9
	par[i] := cur mod (i+1)
	cur := (C*cur+D) mod 10^9
	L[i] := cur mod 10^6

For each v from 0 to N-1, inclusive, compute the value D(v), i.e. the smallest possible sum of distances between the base and all other towns in the subtree T(v). Return the bitwise XOR of all the values D(v).

Definition

Class:: TreeSums
Method:: findSums
Parameters:: int, int, int, int
Returns:: long
Method signature:: long findSums(int N, int seed, int C, int D)
(be sure your method is public)

Constraints

N will be between 1 and 300,000, inclusive.
seed, C and D will be between 0 and 1,000,000,000, inclusive.

Examples

```
6
```
```
8
```
```
3
```
```
13
```
```
Returns: 856320
```
The tree looks as follows: The values of ans(v) are: D(0)=964356, D(1)=964232, D(2)=856204, D(3)=D(4)=D(5)=0. For T(0), the optimal base is town 1. For T(1), the optimal base is also town 1. For each other v, an optimal base for the subtree T(v) is town v. The correct return value is the value (964356 XOR 964232 XOR 856204 XOR 0 XOR 0 XOR 0).
```
2
```
```
10
```
```
20
```
```
30
```
```
Returns: 4630
```
```
6
```
```
55
```
```
1
```
```
18
```
```
Returns: 22
```

999999990

999999990

999999991

Returns: 438628640790

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.