Connection Status:
Competition Arena > TreeSums

TreeSums

SRM 692 · 2016-06-04 · by Xellos0

SRM 692 · 2016-06-04 · by Xellos0 · Graph Theory
Class Name: TreeSums
Return Type: long
Method Name: findSums
Arg Types: (int, int, int, int)
Problem Statement

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).

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
0)
10
1
1
1
Returns: 99
1)
5
310305
116946964
141861
Returns: 1039791
2)
6
6985253
86386005
1
Returns: 3440315
3)
392
6982056
117456126
500000
Returns: 628685472
4)
1
10000
100000
1000000
Returns: 0
20)
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).

Submissions are judged against all 51 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreeSums with a public method long long findSums(int N, int seed, int C, int D) · 51 test cases · 2 s / 256 MB per case

Submitting as anonymous