Problem:


Score : 1800 points

Problem Statement

There is a tree T with N vertices, numbered 1 through N.
For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i.

Snuke is constructing a directed graph T' by arbitrarily assigning direction to each edge in T. (There are 2^{N - 1} different ways to construct T'.)

For a fixed T', we will define d(s,\ t) for each 1 ≤ s,\ t ≤ N, as follows:

d(s,\ t) = (The number of edges that must be traversed against the assigned direction when traveling from vertex s to vertex t)

In particular, d(s,\ s) = 0 for each 1 ≤ s ≤ N.
Also note that, in general, d(s,\ t) ≠ d(t,\ s).

We will further define D as the following:

Snuke is constructing T' so that D will be the minimum possible value.
How many different ways are there to construct T' so that D will be the minimum possible value, modulo 10^9 + 7?

Constraints

2 ≤ N ≤ 1000

1 ≤ a_i,\ b_i ≤ N

The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

Output

Print the number of the different ways to construct T' so that D will be the minimum possible value, modulo 10^9 + 7.

Sample Input 1

4
1 2
1 3
1 4

Sample Output 1

2

The minimum possible value for D is 1.
There are two ways to construct T' to achieve this value, as shown in the following figure:

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

6

The minimum possible value for D is 2.
There are six ways to construct T' to achieve this value, as shown in the following figure:

Sample Input 3

6
1 2
1 3
1 4
2 5
2 6

Sample Output 3

14

Sample Input 4

10
2 4
2 5
8 3
10 7
1 6
2 8
9 5
8 6
10 6

Sample Output 4

102



Sample input:
4
1 2
1 3
1 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
print 2

Submission status: Accepted

Solution code:
# doc: git.io/vy4co
def graph(inp):
    nodes = dict()
    N = None
    for line in inp.splitlines():
        if N is None:
            N = int(line.strip())
            for k in range(1, N + 1):
                nodes[k] = set()
            continue
        i, k = map(int, line.split())
        nodes[i].add(k)
        nodes[k].add(i)
    return nodes

def trace(nodes, start, exclude=None):
    return (start,) + max([trace(nodes, n, exclude=start) for n in nodes[start] if n != exclude], key=len, default=())

def tree(nodes, start, exclude=None):
    return tup([tree(nodes, n, exclude=start) for n in nodes[start] if n != exclude])

class tup(tuple):
    def __new__(cls, arg=()):
        rv = super().__new__(cls, arg)
        rv.height = (1 + min((t.height[0] for t in rv), default=-1),
                     1 + max((t.height[1] for t in rv), default=-1))
        rv.edges = len(rv) + sum(t.edges for t in rv)
        return rv

def combinations(nodes):
    path = trace(nodes, trace(nodes, next(iter(nodes)))[-1])
    D = len(path)
    C = D // 2
    root = path[D // 2]
    if D % 2:
        thetree = tree(nodes, root)
        return sum(enum(limits, thetree) for limits in zip(range(C + 1), reversed(range(C + 1))))
    else:
        left = path[D // 2 - 1]
        left_tree = tup([tree(nodes, left, exclude=root)])
        right_tree = tree(nodes, root, exclude=left)
        lg = [i // 2 for i in range(1, C * 2 + 2)]
        ll = list(zip(lg, reversed(lg)))
        rg = [i // 2 for i in range(C * 2 + 1)]
        rl = list(zip(rg, reversed(rg)))
        tot = 0
        for i in range(len(ll)):
            left_limits = ll[i]
            right_limits = rl[i]
            lrv = enum(left_limits, left_tree) - sum(enum(ne, left_tree) for ne in ll[i - 1: i] + ll[i + 1: i + 2])\
                if sum(left_limits) > C else enum(left_limits, left_tree)
            rrv = enum(right_limits, right_tree)
            tot += lrv * rrv
        return tot

def enum(limits, shape, _cache=dict()):
    limits = tuple(sorted(limits))
    r, b = limits
    low, high = shape.height

    if r >= high:
        return 2 ** shape.edges

    if 0 in limits:
        return 1

    key = hash((r, b, shape))
    if key not in _cache:
        tot = 1
        for subtree in shape:
            acc = 0
            for sublimit in ((r - 1, b), (r, b - 1)):
                acc += enum(sublimit, subtree)
            tot *= acc
        _cache[key] = tot
    return _cache[key]

import sys
sys.setrecursionlimit(99999)
g = graph(sys.stdin.read())
rv = combinations(g)
print(rv % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
print "j"

Submission status: Runtime Error

Solution code:
def build_graph(inp):
    nodes = dict()
    names = dict()
    N = None

    for line in inp:
        # special handling for first line of input -- seed vertices
        if N is None:
            N = int(line.strip())
            for k in range(1, N + 1):
                nodes[k] = set()
                names[id(nodes[k])] = nodes[k]
            continue

        # create edges
        i, k = map(int, line.split())
        nodes[i].add(k)
        nodes[k].add(i)

    return nodes, names


def longest_trace_from(nodes, start, exclude=None):
    traces = [longest_trace_from(nodes, n, exclude=start) for n in nodes[start] if n is not exclude] + [()]
    return (start,) + max(traces, key=len)


def longest_path(nodes):
    """ Find a longest path in the graph:
        Start with a random node, and find a longest trace from there.
        Re-start from the end of that trace and find a lognest trace.
        This will be the longest path in a graph, if graph is a tree. """
    if not nodes:
        return ()
    random = next(iter(nodes))
    start = longest_trace_from(nodes, random)[-1]
    return longest_trace_from(nodes, start)


def shape(nodes, start, exclude=None):
    parts = [shape(nodes, n, exclude=start) for n in nodes[start] if n is not exclude]
    return tuple(sorted(parts))  # any stable order will do


def shape2(nodes, start, exclude=frozenset()):
    parts = [shape(nodes, n, exclude=exclude.union([start])) for n in nodes[start] if n not in exclude]
    return tuple(sorted(parts))  # any stable order will do


def subtree_limits(path):
    L = len(path)
    excl = [frozenset(path[:i][-1:] + path[i + 1:][:1]) for i in range(L)]
    high = [min(i, L - i - 1) for i in range(L)]
    lims = [tuple((H - i, i) for i in range(H // 2 + 1)) for H in high]
    return tuple(dict(start=path[i], exclude=excl[i], limits=lims[i]) for i in range(L))


def combinations(nodes):
    rv = 2
    cache = dict()
    path = longest_path(nodes)
    for d in subtree_limits(path):
        this = d["start"]
        sh = shape2(nodes, d["start"], exclude=d["exclude"])
        for l, r in d["limits"]:
            if not l or not r:
                break  # left == 0 means all right and vv.
        # NOT FINISHED


import pytest
import pprint


def test_sl():
    # pprint.pprint(subtree_limits(tuple(range(9))))  # manual check
    pass


@pytest.fixture
def sample_data1():
    data = """4
              1 2
              1 3
              1 4""".strip().splitlines()
    return build_graph(data)


@pytest.fixture
def nodes(sample_data1):
    nodes, name = sample_data1
    return nodes


def test_com(nodes):
    combinations(nodes)


def test_build(nodes):
    # print(nodes)  # visual inspection
    pass


def test_ltf(nodes):
    assert len(longest_trace_from(nodes, 1)) == 2  # e.g. (1, 2)
    assert len(longest_trace_from(nodes, 2)) == 3  # e.g. (2, 1, 3)


def test_lp(nodes):
    assert len(longest_path(nodes)) == 3  # e.g. (2, 1, 3)