Problem p03348 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
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)
    #print(v, G[v][0], E0, C[-1], len(G[v]))
    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)