Problem:


Score : 1100 points

Problem Statement

Coloring of the vertices of a tree G is called a good coloring when, for every pair of two vertices u and v painted in the same color, picking u as the root and picking v as the root would result in isomorphic rooted trees.

Also, the colorfulness of G is defined as the minimum possible number of different colors used in a good coloring of G.

You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i. We will construct a new tree T by repeating the following operation on this tree some number of times:

Add a new vertex to the tree by connecting it to one of the vertices in the current tree with an edge.

Find the minimum possible colorfulness of T.
Additionally, print the minimum number of leaves (vertices with degree 1) in a tree T that achieves the minimum colorfulness.

Notes

The phrase "picking u as the root and picking v as the root would result in isomorphic rooted trees" for a tree G means that there exists a bijective function f_{uv} from the vertex set of G to itself such that both of the following conditions are met:

f_{uv}(u)=v

For every pair of two vertices (a,b), edge (a,b) exists if and only if edge (f_{uv}(a),f_{uv}(b)) exists.

Constraints

2 \leq N \leq 100

1 \leq a_i,b_i \leq N(1\leq i\leq N-1)

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print two integers with a space in between.
First, print the minimum possible colorfulness of a tree T that can be constructed.
Second, print the minimum number of leaves in a tree that achieves it.

It can be shown that, under the constraints of this problem, the values that should be printed fit into 64-bit signed integers.

Sample Input 1

5
1 2
2 3
3 4
3 5

Sample Output 1

2 4

If we connect a new vertex 6 to vertex 2, painting the vertices (1,4,5,6) red and painting the vertices (2,3) blue is a good coloring.
Since painting all the vertices in a single color is not a good coloring, we can see that the colorfulness of this tree is 2.
This is actually the optimal solution. There are four leaves, so we should print 2 and 4.

Sample Input 2

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

Sample Output 2

3 4

Sample Input 3

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

Sample Output 3

4 6

Sample Input 4

13
5 6
6 4
2 8
4 7
8 9
3 2
10 4
11 10
2 4
13 10
1 8
12 1

Sample Output 4

4 12



Sample input:
5
1 2
2 3
3 4
3 5


Sample output:
2 4

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


def bfs(G, s=0):
    que = deque([s])
    # n = len(G)
    dist = [INF] * n
    par = [-1] * n
    dist[s] = 0
    while que:
        u = que.popleft()
        for v in G[u]:
            if par[u] != v:
                dist[v] = dist[u] + 1
                que += [v]
                par[v] = u
    return dist, par




dist, _ = bfs(G, s=0)
# n = len(G)
ret = -1
for u in range(n):
    if dist[u] > ret:
        ret = dist[u]
        v = u
dist2, par = bfs(G, s=v)
# 直径の長さだけを知りたい時は、return max(dist)
diameter = -1
for i in range(n):
    if dist2[i] > diameter:
        diameter = dist2[i]
        w = i

L  = [0] * (diameter + 1)
now = w
L[0] = w
for i in range(diameter):
    now = par[now]
    L[i + 1] = now

visited = [0] * n
q = [L[diameter // 2]]
visited[L[diameter // 2]] = 1
if diameter % 2:
    q += [L[diameter // 2 + 1]]
    visited[L[diameter // 2 + 1]] = 1


cnt = 2 if diameter % 2 else 1
for k in range(diameter // 2):
    qq = []
    max_deg = 0
    for ii in q:
        if k == 0 and diameter % 2 == 0:
            max_deg = len(G[ii])
        else:
            max_deg = max(max_deg, len(G[ii]) - 1)
        for vv in G[ii]:
            if visited[vv]:
                continue
            visited[vv] = 1
            qq += [vv]
    cnt = cnt * max_deg
    q = qq

print(diameter // 2 + 1, cnt)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

inf = 10**9+7
def dfs(s, Edge):
    dist = [inf]*N
    dist[s] = 0
    stack = [s]
    used = set([s])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1+dist[vn]
                stack.append(vf)
    return dist                

def calc(v1, v2, Dim):
    d1 = dfs(v1, Edge)
    d2 = dfs(v2, Edge)
    di1 = [0]*N
    di2 = [0]*N
    for i in range(N):
        if d1[i] < d2[i]:
            di1[d1[i]] = max(di1[d1[i]], Dim[i] - 1)
        else:
            di2[d2[i]] = max(di2[d2[i]], Dim[i] - 1)
    K = [max(f1, f2) for f1, f2 in zip(di1, di2)]
    res = 1
    for k in K:
        if not k:
            continue
        res = res*k
    return 2*res

N = int(readline())

Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

dist0 = dfs(0, Edge)
vfst = dist0.index(max(dist0))
dist1 = dfs(vfst, Edge)
D = max(dist1)
ans = inf
if D&1:
    C1 = [i for i in range(N) if dist1[i] == D//2]
    C2 = [i for i in range(N) if dist1[i] == D//2+1]
    for c1 in C1:
        for c2 in C2:
            ans = min(ans, calc(c1, c2, Dim))
else:
    c = dist1.index(D//2)
    dic = [0]*N
    dic[0] = Dim[c]
    dc = dfs(c, Edge)
    for i in range(N):
        dic[dc[i]] = max(dic[dc[i]],Dim[i]-1)
    ans = 1
    
    for i in range(N):
        if dic[i]:
            ans = ans*dic[i]
    for vc in Edge[c]:
        ans = min(ans, calc(vc, c, Dim))
print(-(-(D+1)//2), ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

inf = 10**9+7
def dfs(s, Edge):
    dist = [inf]*N
    dist[s] = 0
    stack = [s]
    used = set([s])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1+dist[vn]
                stack.append(vf)
    return dist                

def calc(v1, v2, Dim):
    d1 = dfs(v1, Edge)
    d2 = dfs(v2, Edge)
    di1 = [0]*N
    di2 = [0]*N
    for i in range(N):
        if d1[i] < d2[i]:
            di1[d1[i]] = max(di1[d1[i]], Dim[i] - 1)
        else:
            di2[d2[i]] = max(di2[d2[i]], Dim[i] - 1)
    K = [max(f1, f2) for f1, f2 in zip(di1, di2)]
    res = 1
    for k in K:
        if not k:
            continue
        res = res*k
    return 2*res

N = int(readline())

Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

dist0 = dfs(0, Edge)
vfst = dist0.index(max(dist0))
dist1 = dfs(vfst, Edge)
D = max(dist1)
ans = inf
if D&1:
    C1 = [i for i in range(N) if dist1[i] == D//2]
    C2 = [i for i in range(N) if dist1[i] == D//2+1]
    for c1 in C1:
        for c2 in C2:
            ans = calc(c1, c2, Dim)
else:
    c = dist1.index(D//2)
    dic = [0]*N
    dic[0] = Dim[c]
    dc = dfs(c, Edge)
    for i in range(N):
        dic[dc[i]] = max(dic[dc[i]],Dim[i]-1)
    ans = 1
    
    for i in range(N):
        if dic[i]:
            ans = ans*dic[i]
    for vc in Edge[c]:
        ans = min(ans, calc(vc, c, Dim))
print(-(-(D+1)//2), ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

inf = 10**9+7
def dfs(s, Edge):
    dist = [inf]*N
    dist[s] = 0
    stack = [s]
    used = set([s])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1+dist[vn]
                stack.append(vf)
    return dist                

def calc(v1, v2, Dim):
    d1 = dfs(v1, Edge)
    d2 = dfs(v2, Edge)
    di1 = [0]*N
    di2 = [0]*N
    for i in range(N):
        if d1[i] < d2[i]:
            di1[d1[i]] = max(di1[d1[i]], Dim[i] - 1)
        else:
            di2[d2[i]] = max(di2[d2[i]], Dim[i] - 1)
    K = [max(f1, f2) for f1, f2 in zip(di1, di2)]
    res = 1
    for k in K:
        if not k:
            continue
        res = res*k
    return 2*res

N = int(readline())

Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

dist0 = dfs(0, Edge)
vfst = dist0.index(max(dist0))
dist1 = dfs(vfst, Edge)
D = max(dist1)
ans = inf
if D&1:
    c1 = dist1.index(D//2)
    c2 = dist1.index(D//2+1)
    ans = calc(c1, c2, Dim)
else:
    c = dist1.index(D//2)
    dic = [0]*N
    dic[0] = Dim[c]
    dc = dfs(c, Edge)
    for i in range(N):
        dic[dc[i]] = max(dic[dc[i]],Dim[i]-1)
    ans = 1
    for i in range(N):
        if dic[i]:
            ans = ans*dic[i]
    for vc in Edge[c]:
        ans = min(ans, calc(vc, c, Dim))
print(-(-(D+1)//2), ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import reduce
from itertools import zip_longest
from operator import mul


def dfs(links):
    q = deque([(v, 0) for v in links[0]])
    v = 0
    while q:
        v, a = q.popleft()
        q.extend((u, v) for u in links[v] if u != a)

    anc = [-1] * len(links)
    q = deque([(u, v) for u in links[v]])
    u = 0, 0
    while q:
        u, a = q.popleft()
        anc[u] = a
        q.extend((w, u) for w in links[u] if w != a)

    path = [u]
    a = u
    while a != v:
        a = anc[a]
        path.append(a)
    return path


def calc(links, v, a, l):
    ans = [1] * l
    q = deque([(u, v, 1) for u in links[v] if u != a])
    ans[0] = len(q)
    while q:
        u, a, c = q.popleft()
        ans[c] = max(ans[c], len(links[u]) - 1)
        q.extend((w, u, c + 1) for w in links[u] if w != a)
    return ans


def solve(n, links):
    if n == 2:
        return 1, 0

    path = dfs(links)
    c = len(path)
    l = (len(path) + 1) // 2
    # print('path', path)

    if c % 2 == 0:
        u, v = path[c // 2 - 1], path[c // 2]
        ans1 = calc(links, u, v, l)
        ans2 = calc(links, v, u, l)
        # print('ans12', ans1, ans2)
        leaves = 1
        for a1, a2 in zip(ans1, ans2):
            leaves *= max(a1, a2)
        return len(ans1), leaves * 2
    v = path[c // 2]
    ans0 = calc(links, v, None, l)
    leaves = reduce(mul, ans0, 1)
    # print('ans0', ans0, leaves)
    for u in links[v]:
        ans1 = calc(links, u, v, l)
        ans2 = calc(links, v, u, l)
        tmp = 1
        for a1, a2 in zip_longest(ans1, ans2):
            tmp *= max(a1, a2)
        # print('ans12', ans1, ans2, tmp)
        leaves = min(leaves, tmp * 2)
    return len(ans0), leaves


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(*solve(n, links))

Submission status: Wrong Answer

Solution code:
from collections import deque
from functools import reduce
from itertools import zip_longest
from operator import mul


def dfs(links):
    q = deque([(v, 0) for v in links[0]])
    v = 0
    while q:
        v, a = q.popleft()
        q.extend((u, v) for u in links[v] if u != a)

    anc = [-1] * len(links)
    q = deque([(u, v) for u in links[v]])
    u = 0, 0
    while q:
        u, a = q.popleft()
        anc[u] = a
        q.extend((w, u) for w in links[u] if w != a)

    path = [u]
    a = u
    while a != v:
        a = anc[a]
        path.append(a)
    return path


def calc(links, v, a, l):
    ans = [1] * l
    q = deque([(u, v, 1) for u in links[v] if u != a])
    ans[0] = len(q)
    while q:
        u, a, c = q.popleft()
        ans[c] = max(ans[c], len(links[u]) - 1)
        q.extend((w, u, c + 1) for w in links[u] if w != a)
    return ans


def solve(links):
    path = dfs(links)
    c = len(path)
    l = (len(path) + 1) // 2
    # print('path', path)

    if c % 2 == 0:
        u, v = path[c // 2 - 1], path[c // 2]
        ans1 = calc(links, u, v, l)
        ans2 = calc(links, v, u, l)
        # print('ans12', ans1, ans2)
        leaves = 1
        for a1, a2 in zip(ans1, ans2):
            leaves *= max(a1, a2)
        return len(ans1), leaves * 2
    v = path[c // 2]
    ans0 = calc(links, v, None, l)
    leaves = reduce(mul, ans0, 1)
    # print('ans0', ans0, leaves)
    for u in links[v]:
        ans1 = calc(links, u, v, l)
        ans2 = calc(links, v, u, l)
        tmp = 1
        for a1, a2 in zip_longest(ans1, ans2):
            a1 = 1 if a1 is None else a1
            a2 = 1 if a2 is None else a2
            tmp *= max(a1, a2)
        # print('ans12', ans1, ans2, tmp)
        leaves = min(leaves, tmp * 2)
    return len(ans0), leaves


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(*solve(links))

Submission status: Accepted

Solution code:
import sys

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

ans=(10**15,10**15)

root=-1
depth=[0]*N
Mdata=[0]*100

def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            Mdata[depth[nv]]=max(Mdata[depth[nv]],len(edge[nv])-1)
            dfs(nv,v)

for i in range(N):
    depth=[0]*N
    Mdata=[0]*100
    Mdata[0]=len(edge[i])
    dfs(i,-1)
    tempc=max(depth)+1
    res=1
    for j in range(N):
        if Mdata[j]!=0:
            res*=Mdata[j]
        else:
            break
    ans=min(ans,(tempc,res))

#print(ans)

for i in range(N):
    for j in edge[i]:
        depth=[0]*N
        Mdata=[0]*100
        depth[i]=1
        depth[j]=1
        Mdata[1]=max(len(edge[i]),len(edge[j]))-1
        Mdata[0]=2
        dfs(i,j)
        dfs(j,i)
        tempc=max(depth)
        res=1
        for k in range(N):
            if Mdata[k]!=0:
                res*=Mdata[k]
            else:
                break
        ans=min(ans,(tempc,res))

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

INF = (1<<60)

N = int(input())
graph = [[] for _ in range(N)]
Edges = []
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Edges.append((a-1, b-1))

def bfs(s, noback):
    q = [s]
    D = [-1]*N
    D[s] = 0
    while q:
        qq = []
        for p in q:
            for np in graph[p]:
                if D[np] == -1 and np != noback:
                    D[np] = D[p] + 1
                    qq.append(np)
        q = qq
    
    Ds = [0]*(N+1)
    faraway = 0
    for i, d in enumerate(D):
        faraway = max(faraway, d)
        Ds[d] = max(Ds[d], len(graph[i])-1)
    return Ds, faraway

colorful = INF
nodes = INF

for n in range(N):
    M = [0]*(N+1)
    far = 0
    leaves = 0
    for s in graph[n]:
        leaves += 1
        Ds, faraway = bfs(s, n)
        far = max(far, faraway)
        for i, d in enumerate(Ds):
            M[i] = max(M[i], d)
    color = far + 2
    if color <= colorful:
        if color != colorful:
            nodes = INF
        colorful = color
        for f in range(far):
            leaves *= M[f]
        if leaves < nodes:
            nodes = leaves

for a, b in Edges:
    M = [0]*(N+1)
    leaves = 2
    D1, faraway1 = bfs(a, b)
    for i, d in enumerate(D1):
        M[i] = max(M[i], d)
    
    D2, faraway2 = bfs(b, a)
    for i, d in enumerate(D2):
        M[i] = max(M[i], d)
    
    far = max(faraway1, faraway2)
    color = far + 1
    if color <= colorful:
        if color != colorful:
            nodes = INF
        colorful = color
        for f in range(far):
            leaves *= M[f]
        if leaves < nodes:
            nodes = leaves

print(colorful, nodes)

Submission status: Accepted

Solution code:
from collections import deque


def f(n, dm, g, ind, a, b):
    q = deque([a, b])
    d = [-1] * n
    d[a] = 0
    d[b] = 0
    while q:
        p = q.popleft()
        for node in g[p]:
            if d[node] == -1:
                d[node] = d[p] + 1
                q.append(node)
    l = [0] * (dm // 2 + 1)
    if a == b:
        l[0] = ind[a]
    for i in range(n):
        l[d[i]] = max(l[d[i]], ind[i] - 1)
    res = 1
    for x in l[:-1]:
        res *= x
    return res


n = int(input())
g = [[] for _ in range(n)]
ind = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    ind[a - 1] += 1
    g[b - 1].append(a - 1)
    ind[b - 1] += 1
s = [0]
d = [-1] * n
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            s.append(node)
m = max(d)
idx = d.index(m)
s = [idx]
d1 = [-1] * n
d1[idx] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d1[node] == -1:
            d1[node] = d1[p] + 1
            s.append(node)
diam = max(d1)
idx = d1.index(diam)
s = [idx]
d2 = [-1] * n
d2[idx] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d2[node] == -1:
            d2[node] = d2[p] + 1
            s.append(node)
if diam & 1:  # 直径が奇数
    c = []
    t = diam // 2 + 1
    print(t, end=' ')
    for i in range(n):
        if d1[i] <= t and d2[i] <= t:
            c.append(i)
    ans = f(n, diam, g, ind, c[0], c[1]) * 2
    print(ans)
else:
    t = diam // 2
    print(t + 1, end=' ')
    for i in range(n):
        if d1[i] <= t and d2[i] <= t:
            c = i
    ans = f(n, diam, g, ind, c, c)
    for node in g[c]:
        ans = min(ans, f(n, diam, g, ind, c, node) * 2)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
ansls = []
for i in range(1,n+1):
  root = i
  stack = [i]
  dist = [-1 for i in range(n+1)]
  dist[root] = 0
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        dist[y] = dist[x]+1
        stack.append(y)
  mxd = max(dist)
  dls = [1 for i in range(mxd+1)]
  dls[0] = len(graph[root])
  ans1 = mxd+1
  ans2 = 1
  for j in range(1,n+1):
    d = dist[j]
    dls[d] = max(dls[d],len(graph[j])-1)
  for x in dls:
    ans2 *= x
  ansls.append((ans1,ans2))
for i in range(n-1):
  r1,r2 = ab[i]
  stack = [r1,r2]
  dist = [-1 for i in range(n+1)]
  dist[r1] = 0
  dist[r2] = 0
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        dist[y] = dist[x]+1
        stack.append(y)
  mxd = max(dist)
  dls = [1 for i in range(mxd+1)]
  ans1 = mxd+1
  ans2 = 2
  for j in range(1,n+1):
    d = dist[j]
    dls[d] = max(dls[d],len(graph[j])-1)
  for x in dls:
    ans2 *= x
  ansls.append((ans1,ans2))
ansls.sort()
print(*ansls[0])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    d = [[float("inf")]*n for i in range(n)]
    f = [-1]*n
    for i in range(n):
        d[i][i] = 0
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        d[a][b] = 1
        d[b][a] = 1
        f[a] += 1
        f[b] += 1
        v[a].append(b)
        v[b].append(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                nd = d[i][k]+d[k][j]
                if nd < d[i][j]:
                    d[i][j] = nd

    for i in range(n):
        f[i] = max(f[i],1)
    x = 0
    for i in range(n):
        if d[0][x] < d[0][i]:
            x = i
    y = 0
    for i in range(n):
        if d[x][y] < d[x][i]:
            y = i
    k = (d[x][y]>>1)+1
    ans = float("inf")
    for s in range(n):
        if max(d[s]) < k:
            m = [0]*k
            m[0] = f[s]+1
            for i in range(n):
                fi = f[i]
                di = d[s][i]
                if m[di] < fi:
                    m[di] = fi
            na = 1
            for i in m:
                na *= i
            if na < ans:
                ans = na
        for t in v[s]:
            nd = [min(d[s][i],d[t][i]) for i in range(n)]
            if max(nd) < k:
                m = [0]*k
                m[0] = max(nd[s],nd[t])+1
                for i in range(n):
                    fi = f[i]
                    di = nd[i]
                    if m[di] < fi:
                        m[di] = fi
                na = 2
                for i in m:
                    na *= i
                if na < ans:
                    ans = na
    print(k,ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

inf = 10**9+7
def dfs(s, Edge):
    dist = [inf]*N
    dist[s] = 0
    stack = [s]
    used = set([s])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1+dist[vn]
                stack.append(vf)
    return dist                

def calc(v1, v2, Dim):
    d1 = dfs(v1, Edge)
    d2 = dfs(v2, Edge)
    di1 = [0]*N
    di2 = [0]*N
    for i in range(N):
        if d1[i] < d2[i]:
            di1[d1[i]] = max(di1[d1[i]], Dim[i] - 1)
        else:
            di2[d2[i]] = max(di2[d2[i]], Dim[i] - 1)
    K = [max(f1, f2) for f1, f2 in zip(di1, di2)]
    res = 1
    for k in K:
        if not k:
            continue
        res = res*k
    return 2*res

N = int(readline())

Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

dist0 = dfs(0, Edge)
vfst = dist0.index(max(dist0))
dist1 = dfs(vfst, Edge)
D = max(dist1)
dist0 = dfs(dist1.index(D), Edge)
ans = inf
if D&1:
    C1 = [i for i in range(N) if dist1[i] == D//2 and dist0[i] == D//2+1]
    C2 = [i for i in range(N) if dist1[i] == D//2+1 and dist0[i] == D//2]
    for c1 in C1:
        for c2 in C2:
            ans = min(ans, calc(c1, c2, Dim))
else:
    c = [i for i in range(N) if dist1[i] == D//2 and dist0[i] == D//2]
    c = c[0]
    dic = [0]*N
    dic[0] = Dim[c]
    dc = dfs(c, Edge)
    for i in range(N):
        dic[dc[i]] = max(dic[dc[i]],Dim[i]-1)
    ans = 1
    for i in range(N):
        if dic[i]:
            ans = ans*dic[i]
    for vc in Edge[c]:
        ans = min(ans, calc(vc, c, Dim))
print(-(-(D+1)//2), ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

ab = []
dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ab.append([a,b])

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

ans = float("inf")
ansleef = float("inf")

for r in range(N):

    leef = [0] * N
    
    q = deque([r])
    dep = [float("inf")] * N
    dep[r] = 0
    maxdep = 0

    while len(q) > 0:

        now = q.popleft()
        nchild = 0

        for i in dic[now]:

            if dep[i] > dep[now] + 1:
                nchild += 1
                dep[i] = dep[now] + 1
                maxdep = max(maxdep,dep[i])
                q.append(i)

            leef[dep[now]] = max(leef[dep[now]],nchild)

    if ans > maxdep:
        ans = maxdep

        nl = 1
        for i in range(maxdep):
            nl *= leef[i]

        ansleef = nl

    if ans == maxdep:
        ans = maxdep

        nl = 1
        for i in range(maxdep):
            nl *= leef[i]
        
        ansleef = min(ansleef,nl)

#print (ans + 1,ansleef)

for r in range(N-1):

    leef = [0] * N

    pa = ab[r][0]
    pb = ab[r][1]
    
    q = deque([pa,pb])
    dep = [float("inf")] * N
    dep[pa] = 0
    dep[pb] = 0
    maxdep = 0

    while len(q) > 0:

        now = q.popleft()
        nchild = 0

        for i in dic[now]:

            if dep[i] > dep[now] + 1:
                nchild += 1
                dep[i] = dep[now] + 1
                maxdep = max(maxdep,dep[i])
                q.append(i)

            leef[dep[now]] = max(leef[dep[now]],nchild)

    if ans > maxdep:
        ans = maxdep

        nl = 2
        for i in range(maxdep):
            nl *= leef[i]

        ansleef = nl

    if ans == maxdep:
        ans = maxdep

        nl = 2
        for i in range(maxdep):
            nl *= leef[i]

        ansleef = min(ansleef,nl)

print (ans + 1,ansleef)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
E=[tuple(map(int,input().split())) for i in range(N-1)]

ELIST=[[] for i in range(N+1)]
EDEG=[0]*(N+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)

    EDEG[x]+=1
    EDEG[y]+=1

from collections import deque
Q=deque()
Q.append(1)

H=[-1]*(N+1)
H[1]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H[to]==-1:
            H[to]=H[x]+1
            Q.append(to)

MAXH=max(H)

Q=deque()
xi=H.index(MAXH)
Q.append(xi)

H=[-1]*(N+1)
H[xi]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H[to]==-1:
            H[to]=H[x]+1
            Q.append(to)


MAXH=max(H)

Q=deque()
xi=H.index(MAXH)
Q.append(xi)

H2=[-1]*(N+1)
H2[xi]=0

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if H2[to]==-1:
            H2[to]=H2[x]+1
            Q.append(to)

ANS1=(max(H)+2)//2
print(ANS1)

#print(H)
#print(H2)

if MAXH%2==1:
    Q=deque()
    USE=[0]*(N+1)

    for i in range(N+1):
        if (H[i]==MAXH//2 and H2[i]==MAXH//2+1) or (H[i]==MAXH//2+1 and H2[i]==MAXH//2):
            Q.append(i)
            USE[i]=1

    ANS2=1

    #print(Q)

    while Q:
        NQ=deque()
        score=1
        while Q:
            x=Q.pop()
            USE[x]=1
            score=max(score,len(ELIST[x])-1)

            for to in ELIST[x]:
                if USE[to]==1:
                    continue
                NQ.append(to)

        ANS2*=score
        Q=NQ
            
    print(ANS2*2)

else:
    Q=deque()

    for i in range(N+1):
        if H[i]==MAXH//2 and H2[i]==MAXH//2:
            Q.append(i)
            MID=i

    ANS2=len(ELIST[MID])
    USE=[0]*(N+1)

    #print(Q)

    while Q:
        NQ=deque()
        score=1
        while Q:
            x=Q.pop()
            USE[x]=1
            if x!=MID:
                score=max(score,len(ELIST[x])-1)

            for to in ELIST[x]:
                if USE[to]==1:
                    continue
                NQ.append(to)

        ANS2*=score
        Q=NQ
            
    #print(ANS2)

    Q=deque()
    for j in ELIST[MID]:
        Q.append(j)
        Q.append(MID)
        USE=[0]*(N+1)
        USE[j]=1
        USE[MID]=1

        score2=1

        while Q:
            NQ=deque()
            score=1
            while Q:
                x=Q.pop()
                USE[x]=1
                #if x!=MID and x!=j:
                score=max(score,len(ELIST[x])-1)

                for to in ELIST[x]:
                    if USE[to]==1:
                        continue
                    NQ.append(to)

                #print("!",x,score)

            score2*=score
            Q=NQ

        #print(j,score2)

        ANS2=min(ANS2,score2*2)

    print(ANS2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

"""
・中心が同型不変であることを利用して考える。
・カラフル度はだいたい直径の半分。
・中心が頂点になる場合は、中心を隣接する辺に持ってこれる。Nが小さいので全部計算してもよい
・そもそもすべての辺、頂点に対して、そこを中心とする場合の(色数、葉数)を計算してもよい
"""

N,*AB = map(int,read().split()) 

AB = tuple(zip(*[iter(AB)]*2))

AB

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
deg = [len(x) for x in graph]

graph,deg

def F(centroids):
    """
    ・中心とする1点または2点を与える
    ・できる木の(深さ,葉の数)を返す
    """
    Ncent = len(centroids)
    depth = [None] * (N+1)
    q = centroids
    for x in q: depth[x] = 0
    while q:
        x = q.pop()
        for y in graph[x]:
            if depth[y] is None:
                depth[y] = depth[x] + 1
                q.append(y)
    D = max(depth[1:])
    sep = [1] * (D+1)
    for x in range(1,N+1):
        d = depth[x]
        n = deg[x] - 1
        sep[d] = max(sep[d],n)
    if Ncent == 1:
        sep[0] += 1
    x = 1
    for s in sep[:D]:
        x *= s
    if Ncent == 2:
        x *= 2
    return D+1,x

arr = [F([v]) for v in range(1,N+1)] + [F([a,b]) for a,b in AB]
arr.sort()
answer = arr[0]
print(*answer)