You are not logged in. Please login at to post your questions!


Please explain byteland

There are N cities in Byteland numbered 1 to N with city 1 as the capital. The road network of Byteland has a tree structure. All the roads are bi-directional. Alice and Bob are secret agents working for the Bytelandian Security Agency (BSA). Each secret agent is assigned a random city each month, where he/she must be stationed for the complete month. At the end of each month, they come to the capital to submit their reports to the head of BSA. They always take the shortest path from their city to the capital. If Alice is assigned city A and Bob is assigned city B then they meet at a city C which is common to both their routes to the capital and then travel together from C to the capital.

Alice and Bob wish to spend maximum time together in any trip. So for any pair of assigned cities (A,B) they meet at a city C such that C is the farthest city from the capital and appears in the shortest path from capital to A and capital to B. Since this happens each month they compute this for each pair of assigned cities (A,B) and store it in a matrix M, where M[A][B] = C, the city where they meet.

The importance of a city C(according to Alice and Bob), Im(C) is defined as the number of times C appears in their matrix M. Alice and Bob are interested in finding the importance of each city. Since this output can be large, output the sum S defined as S = (sum i=1 to N) i*Im(i) modulo 1000000007.

Input First line of input contains an integer t (t<=25), the number of test cases. Each test case starts with an integer N (1<=N<=10000), the number of cities The next N-1 lines contain two space separated integers u v (1<=u,v<=N) denoting a road from u to v.

Output For each test case output the required sum S

Example Input: 3 5 1 2 1 3 2 4 2 5 3 1 2 1 3 1

Output: 41 12 1

Explanation For the first test case, the matrix M is: 1 1 1 1 1 1 2 1 2 2 1 1 3 1 1 1 2 1 4 2 1 2 1 2 5

and the corresponding importance array is: 15 7 1 1 1 so the required sum is 115 + 27 + 31 + 41 + 51 = 41 For the second test case, the matrix M is: 1 1 1 1 2 1 1 1 3 and so the Importance array is: 7 1 1 So the required sum is 17 + 21 + 31 = 12

For the third test case, there is only one city, so the Matrix M just has one entry 1, so S = 1


asked 11 Sep '17, 19:30

cursedforever4's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 11 Sep '17, 19:30

question was seen: 361 times

last updated: 11 Sep '17, 19:30