Dividing into Regions
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
ChefLand develops very fast. Recently, there were a few new cities built, so the total number of cities in ChefLand have become N.
In order to communicate, the cities are connected with N-1 bidirectional roads in such a way that there is exactly one way to get from one city to another. In other words, the graph with cities as nodes and roads as edges is a tree.
Now, the King of ChefLand thinks that the country is too big to be ruled by one person, so he decided to split in two parts, each of which will be ruled by one of two his sons. The split should be made by blocking one road. After doing that, there will be two connected parts which will be ruled by sons.
However, not every division is good. In some cases, one of the parts will still be very large, thus, it will be very hard for some of the sons to rule it. So, for every connected part, there's a value called inconvenience. The inconvenience of the part equals to the distance between two most distance cities belonging to this part.
So for every split, there are two inconvenience values that should be calculated. Please help the King to find them!
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
In order not to make this problem I/O related, we will give you the road system in the compressed form. The first and only line of the test case will contain six space-separated integers N, A, B, C, D, E with the following meaning:
- The road system contains N cities and N-1 roads.
- The ith road (1-indexed) connects the cities with the numbers i+1 and ((A + B * (i - 1)) % i) + 1 and has the length equal to (C * i + D) % E.
In order not to make this problem I/O-related, we will ask you the hash function of the answer to each test case.
The hash function is calculated this way:
- 1 ≤ T ≤ 105
- 2 ≤ N, sum of N ≤ 5 × 106
- 0 ≤ A, B, C, D ≤ 104
- 2 ≤ E ≤ 200
Input: 2 5 1 2 3 4 5 89 189 111 34 7 200 Output: 99116027 515191750
Example case 1. The roads are:
- Road connecting cities 1 and 2 with length 2;
- Road connecting cities 2 and 3 with length 0;
- Road connecting cities 3 and 4 with length 3;
- Road connecting cities 4 and 5 with length 1.
If we remove the first road, then the inconveniences of the parts will be equal to 0 and 4. So Q1 = 0, Q2 = 4.
If we remove the second road, the inconveniences will be equal to 2 and 4. So Q3 = 2, Q4 = 4.
If we remove the third road, the inconveniences will be equal to 2 and 1. So Q5 = 1, Q6 = 2.
If we remove the fourth road, the inconveniences will be equal to 5 and 0. So Q7 = 0, Q8 = 5.
So, we've obtained the sequence Q = (0, 4, 2, 4, 1, 2, 0, 5).
By calculating the hash function, we get 0 × 10000030+4 × 10000031+2 × 10000032+4 × 10000033+1 × 10000034+2 × 10000035+0 × 10000036+5 × 10000037 mod (109+7)= 5000105000947004756014371026147026557011640 mod (109+7) = 99116027
Example case 2. This is just a big test case, so that you could check your solution better.
|Tags||bfs, dfs, memoization, snckpb16, tree, xcwgf666|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.