One Node is Gone (Codeforces 1228F)
Tags: Implement, trees

You have an integer $$$n$$$. Let's define following tree generation as McDic's generation:  Make a complete and full binary tree of $$$2^{n} - 1$$$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.  Select a non-root vertex $$$v$$$ from that binary tree.  Remove $$$v$$$ from tree and make new edges between $$$v$$$'s parent and $$$v$$$'s direct children. If $$$v$$$ has no children, then no new edges will be made. You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.

Input: The first line contains integer $$$n$$$ ($$$2 \le n \le 17$$$).The $$$i$$$-th of the next $$$2^{n} - 3$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le 2^{n} - 2$$$) — meaning there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that the given edges form a tree.

Output: Print two lines.In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $$$0$$$.In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.

Note: In the first example, $$$3$$$ is the only possible answer.  In the second example, there are $$$2$$$ possible answers.  In the third example, the tree can't be generated by McDic's generation.

Sample Inputs:
4
1 2
1 3
2 4
2 5
3 6
3 13
3 14
4 7
4 8
5 9
5 10
6 11
6 12

2
1 2

3
1 2
2 3
3 4
4 5
5 6

Sample Outputs:
1
3

2
1 2

0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    visit = [0] * (m + 1)
    visit[s] = 1
    parent = [-1] * (m + 1)
    for k in range(m):
        i = q[k]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)
n = int(input())
m = pow(2, n) - 2
(G, s0) = make_graph(m, m - 1)
if n == 2:
    ans = ['2', '1 2']
    sys.stdout.write('\n'.join(ans))
    exit()
(p, parent) = bfs(1)
cnt = [1] * (m + 1)
for i in p[::-1][:-1]:
    j = parent[i]
    cnt[j] += cnt[i]
l = m // 2
(p, _) = bfs(1)
for _ in range(2):
    u = p[-1]
    (p, parent) = bfs(u)
u = p[-1]
for _ in range(n - 1):
    u = parent[u]
z = [u]
for i in range(s0[u], min(s0[u + 1], s0[u] + 4)):
    z.append(G[i])
ans0 = set()
for u in z:
    (p, parent) = bfs(u)
    cnt = [1] * (m + 1)
    for i in p[::-1][:-1]:
        j = parent[i]
        cnt[j] += cnt[i]
    (ok, i) = ([0] * (m + 1), 0)
    while i <= m:
        ok[i] = 1
        i = i << 1 ^ 1
    (c, v) = (0, u)
    for i in range(1, m + 1):
        if not ok[cnt[i]]:
            c += 1
            if cnt[i] < cnt[v]:
                v = i
    x = [v]
    while x[-1] ^ u:
        x.append(parent[x[-1]])
    f = 1 if len(x) == c else 0
    if s0[v + 1] - s0[v] == 2:
        if cnt[v] ^ 2:
            f = 0
    elif s0[v + 1] - s0[v] == 4:
        y = []
        for i in range(s0[v], s0[v + 1]):
            j = G[i]
            if j ^ parent[v]:
                y.append(cnt[j])
        y.sort()
        if not (ok[y[0]] and ok[y[2]] and (2 * y[0] == 2 * y[1] == y[2] - 1)):
            f = 0
    elif not (s0[v + 1] - s0[v] == 3 and u == v):
        f = 0
    if f:
        for i in x[1:]:
            y = []
            for v in range(s0[i], s0[i + 1]):
                j = G[v]
                if j ^ parent[i]:
                    y.append(cnt[j])
            y.sort()
            if not (len(y) == 2 and ok[y[1]] and (y[1] - y[0] == 1)):
                f = 0
                break
    if f:
        ans0.add(x[0])
ans0 = sorted(list(ans0))
ans = [str(len(ans0)), ' '.join(map(str, ans0))]
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import array
import math
import os
import sys
DEBUG = 'DEBUG' in os.environ

def inp():
    return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)

def solve(N, M, G):
    if N == 2:
        return [0, 1]
    degv = [set() for _ in range(5)]
    for i in range(M):
        d = len(G[i])
        if d == 0 or d >= 5:
            return []
        degv[d].add(i)
    layer_vcount = 1 << N - 1
    vs = degv[1]
    levels = [0] * M
    ans = []
    for level in range(1, N):
        if len(vs) not in (layer_vcount - 1, layer_vcount):
            return []
        if len(vs) == layer_vcount - 1:
            if ans:
                return []
            if level == 1:
                sp_deg_off = -1
            else:
                sp_deg_off = 1
        else:
            sp_deg_off = 0
        ndeg = 3 if level < N - 1 else 2
        us = set()
        ss = set()
        for v in vs:
            levels[v] = level
            p = None
            for u in G[v]:
                if levels[u] == 0:
                    if p is not None:
                        return []
                    p = u
                    break
            if p is None:
                return []
            deg = len(G[p])
            if deg == ndeg:
                us.add(p)
            elif deg == ndeg + sp_deg_off:
                ss.add(p)
            elif sp_deg_off == 0 and deg == ndeg + 1:
                ss.add(p)
            else:
                return []
        if sp_deg_off != 0:
            if len(ss) != 1:
                return []
            (sp,) = list(ss)
            ans = [sp]
            us.add(sp)
        if sp_deg_off == 0:
            if level == N - 2:
                if ss:
                    return []
                if not ans:
                    li = list(us)
                    li.sort()
                    return li
            if len(ss) > 1:
                return []
        vs = us
        layer_vcount >>= 1
    return ans

def main():
    N = int(inp())
    M = (1 << N) - 2
    G = [[] for _ in range(M)]
    for _ in range(M - 1):
        (a, b) = [int(e) - 1 for e in inp().split()]
        G[a].append(b)
        G[b].append(a)
    ans = solve(N, M, G)
    print(len(ans))
    if ans:
        print(*[v + 1 for v in ans])
if __name__ == '__main__':
    main()

Solution (Python):
import array
import math
import os
import sys
DEBUG = 'DEBUG' in os.environ

def inp():
    return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)

def solve(N, M, G):
    if N == 2:
        return [0, 1]
    degv = [set() for _ in range(5)]
    for i in range(M):
        d = len(G[i])
        if d == 0 or d >= 5:
            return []
        degv[d].add(i)
    layer_vcount = 1 << N - 1
    vs = degv[1]
    levels = bytearray(M)
    ans = []
    for level in range(1, N):
        if len(vs) not in (layer_vcount - 1, layer_vcount):
            return []
        if len(vs) == layer_vcount - 1:
            if ans:
                return []
            if level == 1:
                sp_deg_off = -1
            else:
                sp_deg_off = 1
        else:
            sp_deg_off = 0
        ndeg = 3 if level < N - 1 else 2
        us = set()
        ss = set()
        for v in vs:
            levels[v] = level
            p = None
            for u in G[v]:
                if levels[u] == 0:
                    if p is not None:
                        return []
                    p = u
                    break
            if p is None:
                return []
            deg = len(G[p])
            if deg == ndeg:
                us.add(p)
            elif deg == ndeg + sp_deg_off:
                ss.add(p)
            elif sp_deg_off == 0 and deg == ndeg + 1:
                ss.add(p)
            else:
                return []
        if sp_deg_off != 0:
            if len(ss) != 1:
                return []
            (sp,) = list(ss)
            ans = [sp]
            us.add(sp)
        if sp_deg_off == 0:
            if level == N - 2:
                if ss:
                    return []
                if not ans:
                    li = list(us)
                    li.sort()
                    return li
            if len(ss) > 1:
                return []
        vs = us
        layer_vcount >>= 1
    return ans

def main():
    N = int(inp())
    M = (1 << N) - 2
    G = [[] for _ in range(M)]
    for _ in range(M - 1):
        (a, b) = [int(e) - 1 for e in inp().split()]
        G[a].append(b)
        G[b].append(a)
    ans = solve(N, M, G)
    print(len(ans))
    if ans:
        print(*[v + 1 for v in ans])
if __name__ == '__main__':
    main()