Tree with Small Distances (Codeforces 1029E)
Tags: Greedy, graphs

You are given an undirected tree consisting of $$$n$$$ vertices. An undirected tree is a connected undirected graph with $$$n - 1$$$ edges.Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $$$1$$$ to any other vertex is at most $$$2$$$. Note that you are not allowed to add loops and multiple edges.

Input: The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.The following $$$n - 1$$$ lines contain edges: edge $$$i$$$ is given as a pair of vertices $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.

Output: Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $$$1$$$ to any other vertex at most $$$2$$$. Note that you are not allowed to add loops and multiple edges.

Note: The tree corresponding to the first example:  The answer is $$$2$$$, some of the possible answers are the following: $$$[(1, 5), (1, 6)]$$$, $$$[(1, 4), (1, 7)]$$$, $$$[(1, 6), (1, 7)]$$$.The tree corresponding to the second example:  The answer is $$$0$$$.The tree corresponding to the third example:  The answer is $$$1$$$, only one possible way to reach it is to add the edge $$$(1, 3)$$$.

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

7
1 2
1 3
2 4
2 5
3 6
1 7

7
1 2
2 3
3 4
3 5
3 6
3 7

Sample Outputs:
2

0

1

Solution (Python):
from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    p = []
    parent = [1] * (n + 1)
    ok = [0] * (n + 1)
    while q:
        i = q.popleft()
        d = dist[i]
        if d < 3:
            ok[i] = 1
        p.append(i)
        for j in G[i]:
            if dist[j] == -1:
                q.append(j)
                dist[j] = d + 1
                parent[j] = i
    ans = 0
    while p:
        i = p.pop()
        j = parent[i]
        if not ok[i]:
            ok[j] = 1
            ans += 1
            for k in G[j]:
                ok[k] = 1
    return ans
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
ans = bfs(1)
print(ans)

Solution (Python):
from sys import stdin
n = int(stdin.readline())
g = dict()
for i in range(n - 1):
    (u, v) = map(int, stdin.readline().split())
    g.setdefault(u - 1, []).append(v - 1)
    g.setdefault(v - 1, []).append(u - 1)
st = [0]
rank = [0] * n
tree = [0] * n
msk = [0] * n
rd = dict()
while len(st) > 0:
    top = st.pop()
    msk[top] = 1
    for c in g[top]:
        if msk[c] == 0:
            st.append(c)
            tree[c] = top
            rank[c] = rank[top] + 1
            rd.setdefault(rank[c], []).append(c)
max_rank = max(rank)
reach = [0] * n
build = [0] * n
ans = 0
for r in range(max_rank, 2, -1):
    for node in rd[r]:
        if reach[node] == 0:
            reach[node] = 1
            reach[tree[node]] = 1
            reach[tree[tree[node]]] = 1
            build[tree[node]] = 1
print(sum(build))

Solution (Python):
import sys
from collections import deque
mod = 10 ** 9 + 7
INF = float('inf')

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

def inpl():
    return list(map(int, sys.stdin.readline().split()))
n = inp()
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    (a, b) = inpl()
    (a, b) = (a - 1, b - 1)
    edges[a].append(b)
    edges[b].append(a)
dist = [-1] * n
dist[0] = 0
pa = [-1] * n
se = set()
pq = []
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for nx in edges[now]:
        if dist[nx] != -1:
            continue
        pa[nx] = now
        dist[nx] = dist[now] + 1
        if dist[nx] > 2:
            se.add(nx)
            pq.append((dist[nx], nx))
        q.append(nx)
pq = pq[::-1]
res = 0
ind = 0
while se:
    (d, v) = pq[ind]
    ind += 1
    if not v in se:
        continue
    res += 1
    pv = pa[v]
    se.discard(pv)
    for nv in edges[pv]:
        se.discard(nv)
print(res)