Connection Status:
Competition Arena > BearUniqueDiameter

BearUniqueDiameter

SRM 695 · 2016-06-25 · by Errichto

SRM 695 · 2016-06-25 · by Errichto · Brute Force
Class Name: BearUniqueDiameter
Return Type: int
Method Name: countSubtrees
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

A tree is a connected undirected graph without cycles. The distance between two vertices is the number of edges on the unique simple path that connects them. The diameter of a tree is the maximum distance between two of its vertices.


Bears hate ties and love uniqueness. They call a tree nice if there is exactly one unordered pair of vertices (x, y) such that the distance between x and y is equal to the diameter of the tree. (Note that x and y may be identical. In particular, this means that each tree with a single vertex is nice.)


Bear Limak has a tree with N vertices, numbered 0 through N-1. The tree is not necessarily nice. Limak wants to choose some non-empty subtree (i.e., a connected subgraph) of his tree and give it as a gift to someone. Of course, the chosen subtree must be nice.


You are given the description of Limak's tree: the int[]s a and b, each with N-1 elements. For each valid i, there is an edge between vertices a[i] and b[i]. Find and return the number of nice subtrees in Limak's tree, modulo 1,000,000,007.

Notes

  • N will be between 2 and 300, inclusive.
  • a and b will each have exactly N elements.
  • Each element in a and in b will be between 0 and N-1, inclusive.
  • The given N-1 edges will form a tree.

Constraints

    Examples
    0)
    {0,0,0}
{1,2,3}
Returns: 10

    The given tree has 4 vertices and 3 edges: 0-1, 0-2, 0-3. There are the following types of subtrees: The whole tree is also its own subtree. Its diameter is 2. Unfortunately, there is more than one pair of vertices with the distance 2 (the three pairs are: 1-2, 1-3, 2-3). Hence, this subtree is not nice and we don't count it towards the answer. There are 3 subtrees with 3 vertices each. Each of them is nice. There are 3 subtrees with 2 vertices each. Each of them is also nice. Finally, there are 4 subtrees with 1 vertex each. As we already explained above, each of these is nice as well. The answer is 3 + 3 + 4 = 10.

    1)
    {3,2,1,4,0}
{1,3,4,0,5}
Returns: 21
    2)
    {0,1,2,3,2}
{1,2,3,4,5}
Returns: 22
    3)
    {1}
{0}
Returns: 3
    4)
    {36,23,33,33,33,24,33,33,33,33,37,33,33,33,33,28,33,33,22,33,
29,16,33,33,33,33,33,31,35,33,33,8,13,26,12,33,33,0,33,33}
{33,33,0,9,39,33,32,40,15,19,33,30,38,7,25,33,27,11,33,3,33,33,
21,18,5,6,4,33,11,14,10,33,33,33,33,20,2,1,34,17}
Returns: 719477120

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

    Coding Area

    Language: C++17 · define a public class BearUniqueDiameter with a public method int countSubtrees(vector<int> a, vector<int> b) · 36 test cases · 2 s / 256 MB per case

    Submitting as anonymous