Nastia Plays with a Tree (Codeforces 1521D)
Tags: Greedy, dsu

Nastia has an unweighted tree with $$$n$$$ vertices and wants to play with it!The girl will perform the following operation with her tree, as long as she needs:  Remove any existing edge.  Add an edge between any pair of vertices. What is the minimum number of operations Nastia needs to get a bamboo from a tree? A bamboo is a tree in which no node has a degree greater than $$$2$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.Next $$$n - 1$$$ lines of each test cases describe the edges of the tree in form $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$).It's guaranteed the given graph is a tree and the sum of $$$n$$$ in one test doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case in the first line print a single integer $$$k$$$ — the minimum number of operations required to obtain a bamboo from the initial tree.In the next $$$k$$$ lines print $$$4$$$ integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_{2} \le n$$$, $$$x_1 \neq y_1$$$, $$$x_2 \neq y_2$$$) — this way you remove the edge $$$(x_1, y_1)$$$ and add an undirected edge $$$(x_2, y_2)$$$.Note that the edge $$$(x_1, y_1)$$$ must be present in the graph at the moment of removing.

Note: Note the graph can be unconnected after a certain operation.Consider the first test case of the example:    The red edges are removed, and the green ones are added.

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

Sample Outputs:
2
2 5 6 7
3 6 4 5
0

Solution (Python):
def dfs(x, e, v, g):
    v[x] = True
    c = 0
    for y in e[x]:
        if not y in v:
            if dfs(y, e, v, g):
                c += 1
                if c > 2:
                    g.append((x, y))
            else:
                g.append((x, y))
    if c < 2:
        return True
    if x != 1:
        return False

def leaf(x, e):
    p = 0
    while True:
        u = 0
        for y in e[x]:
            if y != p:
                u = y
                break
        if u == 0:
            break
        p = x
        x = u
    return x

def solve(n, e):
    g = []
    dfs(1, e, {}, g)
    for (x, y) in g:
        e[x].remove(y)
        e[y].remove(x)
    z = []
    l = leaf(1, e)
    for (p, y) in g:
        r = leaf(y, e)
        z.append((p, y, l, r))
        l = leaf(r, e)
    print(len(z))
    if len(z) > 0:
        print('\n'.join(map(lambda x: ' '.join(map(str, x)), z)))

def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        e = {}
        for i in range(n - 1):
            (a, b) = map(int, input().split())
            if not a in e:
                e[a] = []
            if not b in e:
                e[b] = []
            e[a].append(b)
            e[b].append(a)
        solve(n, e)
import threading
import sys
sys.setrecursionlimit(10 ** 5 + 1)
threading.stack_size(262000)
main = threading.Thread(target=main)
main.start()
main.join()

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()
    graph = [set() for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readInts()
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)
    ans = []
    st = [(0, 0)]
    par = [-1] * n
    par[0] = -2
    while st:
        (node, marked) = st.pop()
        if marked:
            if node == 0:
                m = len(graph[node])
                if m <= 1:
                    continue
                if m > 2:
                    cnt = 0
                    de = []
                    for nei in graph[node]:
                        de.append((nei, node))
                        cnt += 1
                        if cnt == m - 2:
                            break
                    while de:
                        (nei, node) = de.pop()
                        ans.append([nei, node, 0, 0])
                        graph[node].remove(nei)
                        graph[nei].remove(node)
            else:
                m = len(graph[node]) - 1
                if m <= 1:
                    continue
                graph[node].remove(par[node])
                graph[par[node]].remove(node)
                ans.append([node, par[node], 0, 0])
                if m > 2:
                    cnt = 0
                    de = []
                    for nei in graph[node]:
                        de.append((nei, node))
                        cnt += 1
                        if cnt == m - 2:
                            break
                    while de:
                        (nei, node) = de.pop()
                        ans.append([nei, node, 0, 0])
                        graph[node].remove(nei)
                        graph[nei].remove(node)
        else:
            st.append((node, 1))
            for nei in graph[node]:
                if par[nei] == -1:
                    par[nei] = node
                    st.append((nei, 0))
    vis = [0] * n
    arr = []
    for i in range(n):
        if vis[i]:
            continue
        vis[i] = 1
        if len(graph[i]) == 1:
            st = i
        elif len(graph[i]) == 0:
            arr.append((i, i))
            continue
        else:
            st = list(graph[i])[0]
            vis[st] = 1
            stack = [st]
            while stack:
                node = stack.pop()
                dst = node
                for nei in graph[node]:
                    if not vis[nei]:
                        vis[nei] = 1
                        stack.append(nei)
            st = dst
        stack = [i]
        while stack:
            node = stack.pop()
            dst = node
            for nei in graph[node]:
                if not vis[nei]:
                    vis[nei] = 1
                    stack.append(nei)
        arr.append((st, dst))
    k = len(arr)
    for i in range(k - 1):
        (ans[i][2], ans[i][3]) = (arr[i][1], arr[i + 1][0])
    print(len(ans))
    for (x, y, u, v) in ans:
        print(x + 1, y + 1, u + 1, v + 1)
for _ in range(readInt()):
    solve()

Solution (Python):
import threading
import sys
sys.setrecursionlimit(10 ** 5 + 1)
threading.stack_size(262000)

def dfs(x, e, v, g):
    v[x] = True
    c = 0
    for y in e[x]:
        if y not in v:
            if dfs(y, e, v, g):
                c += 1
                if c > 2:
                    g.append((x, y))
            else:
                g.append((x, y))
    if c < 2:
        return True
    if x != 1:
        return False

def leaf(x, e):
    p = 0
    while True:
        u = 0
        for y in e[x]:
            if y != p:
                u = y
                break
        if u == 0:
            break
        p = x
        x = u
    return x

def main():
    for _ in range(int(input())):
        n = int(input())
        e = {}
        for i in range(n - 1):
            (a, b) = map(int, input().split())
            e[a] = e.get(a, []) + [b]
            e[b] = e.get(b, []) + [a]
        g = []
        dfs(1, e, {}, g)
        for (x, y) in g:
            e[x].remove(y)
            e[y].remove(x)
        z = []
        l = leaf(1, e)
        for (p, y) in g:
            r = leaf(y, e)
            z.append((p, y, l, r))
            l = leaf(r, e)
        print(len(z))
        if len(z) > 0:
            print('\n'.join(map(lambda x: ' '.join(map(str, x)), z)))
main = threading.Thread(target=main)
main.start()
main.join()