Восстанови дерево по коду прюфера . (12,13,13,11,6...

python
prufer = [12,13,13,11,6,15,8,9,15,12,12,16,18,18,19,19,18]
n = len(prufer)+2
n

19

python
from collections import Counter
degree = Counter({i:1 for i in range(1,n+1)})
for v in prufer:
    degree[v]+=1
edges=[]
for v in prufer:
    # find smallest vertex with degree 1
    leaf = min([x for x in range(1,n+1) if degree[x]==1])
    edges.append((leaf,v))
    degree[leaf]-=1
    degree[v]-=1
# last edge between the two remaining nodes with degree 1
remaining=[x for x in range(1,n+1) if degree[x]==1]
edges.append(tuple(remaining))
edges

[(1, 12),
 (2, 13),
 (3, 13),
 (4, 11),
 (5, 6),
 (6, 15),
 (7, 8),
 (8, 9),
 (9, 15),
 (10, 12),
 (11, 12),
 (12, 16),
 (13, 18),
 (14, 18),
 (15, 19),
 (16, 19),
 (17, 18),
 (18, 19)]

python
edges = [(1,12),(2,13),(3,13),(4,11),(5,6),(6,15),(7,8),(8,9),(9,15),(10,12),(11,12),(12,16),(13,18),(14,18),(15,19),(16,19),(17,18),(18,19)]
n=19
from collections import defaultdict
adj=defaultdict(list)
for u,v in edges:
    adj[u].append(v)
    adj[v].append(u)
# compute centroid
def centroid(n, adj):
    best=None
    minmax=n
    parent=[0]*(n+1)
    size=[0]*(n+1)
    def dfs(u, p):
        size[u]=1
        max_sub=0
        for v in adj[u]:
            if v==p: continue
            dfs(v,u)
            size[u]+=size[v]
            max_sub=max(max_sub,size[v])
        max_sub=max(max_sub,n-size[u])
        nonlocal best,minmax
        if max_sub<minmax:
            minmax=max_sub
            best=u
        return
    dfs(1,0)
    return best,minmax
centroid(n,adj)


(19, 6)

python
def centroid_all(n,adj):
    size=[0]*(n+1)
    best=[]
    minmax=n
    def dfs(u,p):
        nonlocal minmax,best
        size[u]=1
        max_sub=0
        for v in adj[u]:
            if v==p: continue
            dfs(v,u)
            size[u]+=size[v]
            max_sub=max(max_sub,size[v])
        max_sub=max(max_sub,n-size[u])
        if max_sub<minmax:
            minmax=max_sub
            best=[u]
        elif max_sub==minmax:
            best.append(u)
    dfs(1,0)
    return best,minmax
centroid_all(n,adj)


([19], 6)

python
def subtree_size(u,p,adj):
    s=1
    for v in adj[u]:
        if v==p: continue
        s+=subtree_size(v,u,adj)
    return s
neigh_sizes=[]
for v in adj[19]:
    neigh_sizes.append(subtree_size(v,19,adj))
neigh_sizes, sum(neigh_sizes)


([6, 6, 6], 18)

python
def max_component_size(root):
    size=[0]*(n+1)
    def dfs(u,p):
        size[u]=1
        for v in adj[u]:
            if v==p: continue
            dfs(v,u)
            size[u]+=size[v]
    dfs(root,0)
    best=0
    for v in range(1,n+1):
        sizes=[]
        for nb in adj[v]:
            if size[nb]<size[v]:  # neighbor is in subtree under v
                sizes.append(size[nb])
            else:
                sizes.append(n-size[v])
        best=max(best,*sizes)
    return best
max_component_size(12)


18

python
deg=[0]*(n+1)
for u in range(1,n+1):
    deg[u]=len(adj[u])
from collections import deque
leaves=deque([u for u in range(1,n+1) if deg[u]==1])
removed=0
layer=0
remain=set(range(1,n+1))
while len(remain)>2:
    layer+=1
    for _ in range(len(leaves)):
        leaf=leaves.popleft()
        remain.remove(leaf)
        removed+=1
        for nb in adj[leaf]:
            if nb in remain:
                deg[nb]-=1
                if deg[nb]==1:
                    leaves.append(nb)
    # break if remain<=2
remain,len(remain),removed


({19}, 1, 18)