Problem: 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.

Submission attempts (in order):
N = int(input())
G = [[] for i in range(N)]
E9 = []
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    E9.append((a-1, b-1))

def encode(v, p):
    res = []
    tmp = []
    l = 0
    P = []
    def edfs(v, p):
        res = [0]
        cs = []
        for w in G[v]:
            if w == p:
                continue
            cs.append(edfs(w, v))
        cs.sort()
        for c in cs:
            res.extend(c)
        res.append(1)
        return res
    E = edfs(v, p)
    return E

def calc(E):
    st = []
    C = [0]
    P = []
    L = len(E)
    l = 0
    for i in range(L):
        if i and E[i-1] < E[i]:
            l += 1
        if E[i] == 0:
            st.append(i)
            P.append(None)
        else:
            j = st.pop()
            P.append(i)
            #P[i] = j
            P[j] = i
        C.append(l)
    return C, P

INF = 10**9
def merge(e1, e2):
    l1 = len(e1); l2 = len(e2)
    dp = [[0] * (l1+1) for i in range(l2+1)]

    C1, P1 = calc(e1)
    C2, P2 = calc(e2)

    prev = {}
    memo = {}
    def dfs(x, y):
        if (x, y) in memo:
            return memo[x, y]
        if x == l1 and y == l2:
            return 0
        res = INF
        p = None
        if x < l1 and y < l2 and e1[x] == e2[y]:
            r = dfs(x+1, y+1) + max(C1[x+1]-C1[x], C2[y+1]-C2[y])
            if r < res:
                res = r
                p = (x+1, y+1)
        if x < l1 and e1[x] == 0:
            r = dfs(P1[x]+1, y) + C1[P1[x]+1] - C1[x]
            if r < res:
                res = r
                p = (P1[x]+1, y)
        if y < l2 and e2[y] == 0:
            r = dfs(x, P2[y]+1) + C2[P2[y]+1] - C2[y]
            if r < res:
                res = r
                p = (x, P2[y]+1)
        memo[x, y] = res
        prev[x, y] = p
        return res
    prev[0, 0] = (0, 0)
    r = dfs(0, 0)
    v = (0, 0)
    res = []
    while v != (l1, l2):
        print(v)
        px, py = v
        x, y = v = prev[v]
        if px != x and py != y:
            res.append(e1[px])
        elif px != x:
            res.extend(e1[px:x])
        else:
            res.extend(e2[py:y])
    print(res)
    return r, res

from collections import deque
def bfs(v, p=-1):
    que = deque([v])
    dist = {v: 0, p: 0}
    prev = {}
    while que:
        u = que.popleft()
        d = dist[u]
        for w in G[u]:
            if w not in dist:
                dist[w] = d + 1
                prev[w] = u
                que.append(w)
    w = u
    res = []
    while w != v:
        res.append(w)
        w = prev[w]
    res.append(v)
    return u, res
def solve(u, v):
    if bfs(u, v) > (L+1)//2 < bfs(v, u):
        return 10**9
    E1 = encode(u, v)
    E2 = encode(v, u)
    #print(u, v, E1, E2)
    return merge(E1, E2)[0]*2
def vsolve(v):
    if bfs(u) > (L+1)//2:
        return 10**9
    E0 = encode(G[v][0], v)
    for w in G[v][1:]:
        E1 = encode(w, w)
        _, E0 = merge(E0, E1)
    C, P = calc(E0)
    
    return C[-1]*len(G[v])
v, _ = bfs(0)
w, D = bfs(v)
L = len(D)

col = (L + 1) // 2

ans = 10**18
for a, b in E9:
    ans = min(ans, solve(a, b))
for v in range(N):
    ans = min(ans, vsolve(v))
print(col, ans)


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

from collections import deque
def bfs(v):
    que = deque([v])
    dist = {v: 0}
    prev = {v: v}
    while que:
        u = que.popleft()
        d = dist[u]
        for w in G[u]:
            if w in dist:
                continue
            dist[w] = d + 1
            prev[w] = u
            que.append(w)
    w = u
    D = []
    while w != v:
        D.append(w)
        w = prev[w]
    D.append(v)
    return u, D

from collections import deque
def solve(u, v = -1):
    que = deque([u])
    if v != -1:
        que.append(v)
    used = set([u, v])
    D = {v: 0, u: 0}
    E = {}
    if v != -1:
        E[0] = max(len(G[v]), len(G[u]))-1
    else:
        E[0] = len(G[u])
    x = v
    while que:
        v = que.popleft()
        d = D[v]
        for w in G[v]:
            if w in used:
                continue
            D[w] = d + 1
            que.append(w)
            used.add(w)
            E[d+1] = max(E.get(d+1, 0), len(G[w])-1)
    res = 2 if x != -1 else 1
    for v in E.values():
        if v: res *= v
    return res

D = bfs(bfs(0)[0])[1]
L = len(D)

col = (L + 1) // 2

if L % 2 == 1:
    ans = 10**18
    v = D[L//2]
    for w in G[v]:
        ans = min(ans, solve(v, w))
    ans = min(ans, solve(v))
else:
    v = D[L//2-1]; w = D[L//2]
    ans = solve(v, w)
print(col, ans)


Verdicts: Runtime Error

Accepted