Complete Mirror (Codeforces 1182D)
Tags: Implement, hashing

You have given tree consist of $$$n$$$ vertices. Select a vertex as root vertex that satisfies the condition below.  For all vertices $$$v_{1}$$$ and $$$v_{2}$$$, if $$$distance$$$($$$root$$$, $$$v_{1}$$$) $$$= distance$$$($$$root$$$, $$$v_{2})$$$ then $$$degree$$$($$$v_{1}$$$) $$$= degree$$$($$$v_{2}$$$), where $$$degree$$$ means the number of vertices connected to that vertex, and $$$distance$$$ means the number of edges between two vertices. Determine and find if there is such root vertex in the tree. If there are multiple answers, find any of them.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the number of vertices.Each of the next $$$n-1$$$ lines contains two integers $$$v_{i}$$$ and $$$u_{i}$$$ ($$$1 \le v_{i} \lt u_{i} \le n$$$) — it means there is an edge exist between $$$v_{i}$$$ and $$$u_{i}$$$. It is guaranteed that the graph forms tree.

Output: If there is such root vertex exists, print any of them. Otherwise, print $$$-1$$$.

Note: This is the picture for the first example. $$$1$$$, $$$5$$$, $$$7$$$ also can be a valid answer.  This is the picture for the second example. You can see that it's impossible to find such root vertex.  

Sample Inputs:
7
1 2
2 3
3 4
4 5
3 6
6 7

6
1 3
2 3
3 4
4 5
4 6

Sample Outputs:
3

-1

Solution (Python):
def longest_path():
    try:
        d = [-1 for _ in range(n)]
        d[0] = 0
        q = [0]
        for i in range(n):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    q.append(t)
                    d[t] = d[f] + 1
        u = q[-1]
        d = [-1 for _ in range(n)]
        p = [-1 for _ in range(n)]
        d[u] = 0
        q = [u]
        for i in range(n):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    q.append(t)
                    d[t] = d[f] + 1
                    p[t] = f
        v = q[-1]
        ld = d[v]
        w = v
        if ld & 1:
            return (u, v, None)
        while d[w] != ld >> 1:
            w = p[w]
        return (u, v, w)
    except:
        print(f'Error raised in longest_path()')

def top(u):
    try:
        if u is None:
            return False
        dist = [-1 for _ in range(n)]
        deg = [-1 for _ in range(n)]
        dist[u] = 0
        q = [u]
        for i in range(n):
            f = q[i]
            if deg[dist[f]] == -1:
                deg[dist[f]] = len(g[f])
            elif len(g[f]) != deg[dist[f]]:
                return False
            for t in g[f]:
                if dist[t] == -1:
                    q.append(t)
                    dist[t] = dist[f] + 1
        return True
    except:
        print(f'Error raised in top({u})')

def semitop(w):
    try:
        if w is None:
            return (False, None)
        d = [-1 for _ in range(n)]
        d[w] = 0
        q = [w]
        i = 0
        while i < len(q):
            f = q[i]
            for t in g[f]:
                if d[t] == -1:
                    if len(g[t]) != 2:
                        d[t] = 100500
                        if top(t):
                            return (True, t)
                    else:
                        d[t] = d[f] + 1
                        q.append(t)
            i += 1
        return (False, None)
    except:
        print(f'Error raised in semitop({w})')
try:
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = map(lambda _: int(_) - 1, input().split())
        g[u].append(v)
        g[v].append(u)
    (u, v, w) = longest_path()
    if top(u):
        print(u + 1)
    elif top(v):
        print(v + 1)
    elif top(w):
        print(w + 1)
    else:
        (k, t) = semitop(w)
        if k:
            print(t + 1)
        else:
            print(-1)
except:
    print(f'Error raised in main')

Solution (Python):
from collections import deque
n = int(input())
e = [[] for i in range(n + 1)]
for i in range(n - 1):
    (u, v) = map(int, input().split())
    e[u].append(v)
    e[v].append(u)
dep = [-1] * (n + 1)
dep[1] = 0
q = deque([1])
cur = 1
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
dep = [-1] * (n + 1)
pred = [0] * (n + 1)
dep[cur] = 0
q = deque([cur])
end = cur
while q:
    end = q.popleft()
    for to in e[end]:
        if dep[to] == -1:
            dep[to] = dep[end] + 1
            pred[to] = end
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(cur)
    exit()
center = end
for i in range(dep[end] // 2):
    center = pred[center]
dep = [-1] * (n + 1)
dep[end] = 0
q = deque([end])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(end)
    exit()
top = center
dep = [-1] * (n + 1)
dep[center] = 0
q = deque([center])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            if len(e[to]) == 2:
                dep[to] = dep[cur] + 1
                q.append(to)
            elif len(e[to]) == 1:
                top = to
                q.clear()
                break
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(center)
    exit()
dep = [-1] * (n + 1)
dep[top] = 0
q = deque([top])
while q:
    cur = q.popleft()
    for to in e[cur]:
        if dep[to] == -1:
            dep[to] = dep[cur] + 1
            q.append(to)
deg = [-1] * (n + 1)
bad = False
for i in range(1, n + 1):
    if deg[dep[i]] == -1:
        deg[dep[i]] = len(e[i])
    elif deg[dep[i]] != len(e[i]):
        bad = True
        break
if not bad:
    print(top)
    exit()
print(-1)

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]
    dist = [inf] * (n + 1)
    dist[s] = 0
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
    return (q, dist)

def ok(dist):
    c = [0] * (n + 1)
    for i in range(1, n + 1):
        j = dist[i]
        if not c[j]:
            c[j] = s0[i + 1] - s0[i]
        if c[j] ^ s0[i + 1] - s0[i]:
            return False
    return True
n = int(input())
if n == 1:
    ans = 1
    print(ans)
    exit()
(G, s0) = make_graph(n, n - 1)
inf = pow(10, 9) + 1
(_, du) = bfs(1)
v = du.index(max(du[1:]))
(_, dv) = bfs(v)
u = dv.index(max(dv[1:]))
(_, du) = bfs(u)
ans = -1
if ok(du):
    ans = u
elif ok(dv):
    ans = v
else:
    w = 0
    for i in range(1, n + 1):
        if 2 * du[i] == 2 * dv[i] == du[v]:
            w = i
    if w:
        (p, dw) = bfs(w)
        if ok(dw):
            ans = w
        cnt = [1] * (n + 1)
        cnt[0] = inf
        for i in p[::-1]:
            for v in range(s0[i], s0[i + 1]):
                j = G[v]
                if dw[i] < dw[j]:
                    cnt[i] += cnt[j]
        (w, i) = (0, w)
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if cnt[j] < cnt[w]:
                w = j
        f = 1
        while f:
            f = 0
            for v in range(s0[w], s0[w + 1]):
                j = G[v]
                if dw[w] < dw[j]:
                    w = j
                    f = 1
                    break
        (_, dw) = bfs(w)
        if ok(dw):
            ans = w
print(ans)