Begginer's Zelda (Codeforces 1905B)
Tags: Greedy, trees

You are given a tree$$$^{\dagger}$$$. In one zelda-operation you can do follows: Choose two vertices of the tree $$$u$$$ and $$$v$$$; Compress all the vertices on the path from $$$u$$$ to $$$v$$$ into one vertex. In other words, all the vertices on path from $$$u$$$ to $$$v$$$ will be erased from the tree, a new vertex $$$w$$$ will be created. Then every vertex $$$s$$$ that had an edge to some vertex on the path from $$$u$$$ to $$$v$$$ will have an edge to the vertex $$$w$$$.  Illustration of a zelda-operation performed for vertices $$$1$$$ and $$$5$$$. Determine the minimum number of zelda-operations required for the tree to have only one vertex.$$$^{\dagger}$$$A tree is a connected acyclic undirected graph.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices.$$$i$$$-th of the next $$$n − 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the numbers of vertices connected by the $$$i$$$-th edge.It is guaranteed that the given edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

Note: In the first test case, it's enough to perform one zelda-operation for vertices $$$2$$$ and $$$4$$$.In the second test case, we can perform the following zelda-operations:  $$$u = 2, v = 1$$$. Let the resulting added vertex be labeled as $$$w = 10$$$;  $$$u = 4, v = 9$$$. Let the resulting added vertex be labeled as $$$w = 11$$$;  $$$u = 8, v = 10$$$. After this operation, the tree consists of a single vertex. 

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

Sample Outputs:
1
3
2
2

Solution (Python):
import sys

def solve():
    n = inp()
    freq = [0] * (n + 1)
    for i in range(1, n):
        (u, v) = invr()
        freq[u] += 1
        freq[v] += 1
    cnt = 0
    for i in range(1, n + 1):
        if freq[i] == 1:
            cnt += 1
    res = (cnt + 1) // 2
    print(res)

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    testcases = 1
    testcases = inp()
    for each_testcase in range(1, testcases + 1):
        solve()
    if not ONLINE_JUDGE:
        sys.stdout.close()

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    return input().strip()

def invr():
    return map(int, input().split())
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    n = readInt()
    deg = [0] * n
    for _ in range(n - 1):
        (u, v) = readInts()
        deg[u - 1] += 1
        deg[v - 1] += 1
    return (sum([d == 1 for d in deg]) + 1) // 2
for _ in range(int(input())):
    print(solve())

Solution (Python):
import collections
import sys
import heapq
import bisect
import math
input = sys.stdin.readline

def solve():
    n = int(input())
    degree = [0] * (n + 1)
    for _ in range(n - 1):
        (u, v) = map(int, input().split())
        degree[u] += 1
        degree[v] += 1
    leafs = []
    for i in range(1, n + 1):
        if degree[i] == 1:
            leafs.append(i)
    print(len(leafs) // 2 + len(leafs) % 2)
t = int(input())
for i in range(t):
    solve()