Andrey's Tree (Codeforces 1935F)
Tags: Greedy, dsu

Master Andrey loves trees$$$^{\dagger}$$$ very much, so he has a tree consisting of $$$n$$$ vertices.But it's not that simple. Master Timofey decided to steal one vertex from the tree. If Timofey stole vertex $$$v$$$ from the tree, then vertex $$$v$$$ and all edges with one end at vertex $$$v$$$ are removed from the tree, while the numbers of other vertices remain unchanged. To prevent Andrey from getting upset, Timofey decided to make the resulting graph a tree again. To do this, he can add edges between any vertices $$$a$$$ and $$$b$$$, but when adding such an edge, he must pay $$$|a - b|$$$ coins to the Master's Assistance Center.Note that the resulting tree does not contain vertex $$$v$$$.Timofey has not yet decided which vertex $$$v$$$ he will remove from the tree, so he wants to know for each vertex $$$1 \leq v \leq n$$$, the minimum number of coins needed to be spent to make the graph a tree again after removing vertex $$$v$$$, as well as which edges need to be added.$$$^{\dagger}$$$A tree is an undirected connected graph without cycles.

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$$$ ($$$5 \le n \le 2\cdot10^5$$$) — the number of vertices in Andrey's tree.The next $$$n - 1$$$ lines contain a description of the tree's edges. The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — 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 $$$2\cdot10^5$$$.

Output: For each test case, output the answer in the following format:For each vertex $$$v$$$ (in the order from $$$1$$$ to $$$n$$$), in the first line output two integers $$$w$$$ and $$$m$$$ — the minimum number of coins that need to be spent to make the graph a tree again after removing vertex $$$v$$$, and the number of added edges.Then output $$$m$$$ lines, each containing two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n, a \ne v, b \ne v$$$, $$$a \ne b$$$) — the ends of the added edge.If there are multiple ways to add edges, you can output any solution with the minimum cost.

Note: In the first test case:Consider the removal of vertex $$$4$$$:  The optimal solution would be to add an edge from vertex $$$5$$$ to vertex $$$3$$$. Then we will spend $$$|5 - 3| = 2$$$ coins.In the third test case:Consider the removal of vertex $$$1$$$:  The optimal solution would be:   Add an edge from vertex $$$2$$$ to vertex $$$3$$$, spending $$$|2 - 3| = 1$$$ coin.  Add an edge from vertex $$$3$$$ to vertex $$$4$$$, spending $$$|3 - 4| = 1$$$ coin.  Add an edge from vertex $$$4$$$ to vertex $$$5$$$, spending $$$|4 - 5| = 1$$$ coin. Then we will spend a total of $$$1 + 1 + 1 = 3$$$ coins.Consider the removal of vertex $$$2$$$:  No edges need to be added, as the graph will remain a tree after removing the vertex.

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

Sample Outputs:
1 1
3 4

0 0

1 1
1 2

2 1
3 5

0 0

0 0

0 0

1 1
1 2

1 1
1 2

1 1
1 2

3 3
2 3
4 5
3 4

0 0

0 0

0 0

0 0

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

def solve():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = [int(x) - 1 for x in input().split()]
        G[u].append(v)
        G[v].append(u)
    order = [0]
    par = [-1] * n
    for i in range(n):
        u = order[i]
        for v in G[u]:
            if v == par[u]:
                continue
            par[v] = u
            order.append(v)
    max_sub = list(range(n))
    min_sub = list(range(n))
    mx = [[0, 0] for _ in range(n)]
    mn = [[n, n] for _ in range(n)]
    for i in range(n - 1, 0, -1):
        u = order[i]
        p = par[u]
        curr_mx = max_sub[u]
        curr_mn = min_sub[u]
        max_sub[p] = max(max_sub[p], curr_mx)
        min_sub[p] = min(min_sub[p], curr_mn)
        for j in range(2):
            if curr_mx > mx[p][j]:
                (curr_mx, mx[p][j]) = (mx[p][j], curr_mx)
            if curr_mn < mn[p][j]:
                (curr_mn, mn[p][j]) = (mn[p][j], curr_mn)
    max_up = [-1] * n
    min_up = [n] * n
    for i in range(1, n):
        u = order[i]
        p = par[u]
        max_up[u] = max(p, max_up[p])
        min_up[u] = min(p, min_up[p])
        if max_sub[u] == mx[p][0]:
            max_up[u] = max(max_up[u], mx[p][1])
        else:
            max_up[u] = max(max_up[u], mx[p][0])
        if min_sub[u] == mn[p][0]:
            min_up[u] = min(min_up[u], mn[p][1])
        else:
            min_up[u] = min(min_up[u], mn[p][0])
    res = []
    for u in range(n):
        ans = len(G[u]) - 1
        edges = []
        components = []
        for v in G[u]:
            if v == par[u]:
                components.append((min_up[u], max_up[u]))
            else:
                components.append((min_sub[v], max_sub[v]))
        components.sort()
        for i in range(1, len(components)):
            (l, r) = components[i]
            if l > u:
                break
            edges.append((l - 1, l))
        components.sort(key=lambda x: -x[1])
        parts_connected = components[0][0] < u
        for i in range(1, len(components)):
            (l, r) = components[i]
            if r < u:
                break
            if l > u or not parts_connected:
                edges.append((r, r + 1))
            if l < u:
                parts_connected = True
        if not parts_connected and 0 < u < n - 1:
            ans += 1
            edges.append((u - 1, u + 1))
        edges = [f'{e[0] + 1} {e[1] + 1}' for e in edges]
        res.append(f'{ans} {len(edges)}')
        res.append('\n'.join(edges))
    return '\n'.join(map(str, res))
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

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

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

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

def insr():
    s = input()
    return list(s[:len(s) - 1])

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

def solution():
    n = inp()
    tree = collections.defaultdict(list)
    for i in range(n - 1):
        (u, v) = inlt()
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)
    parents = [-1] * n
    travel = [0]
    cur_idx = 0
    while cur_idx < len(travel):
        cur_node = travel[cur_idx]
        cur_idx += 1
        for nxt_node in tree[cur_node]:
            if nxt_node == parents[cur_node]:
                continue
            parents[nxt_node] = cur_node
            travel.append(nxt_node)
    max_edges = collections.defaultdict(int)
    min_edges = collections.defaultdict(int)
    for cur_node in travel[1:][::-1]:
        cur_max = cur_node
        cur_min = cur_node
        for nxt_node in tree[cur_node]:
            if nxt_node == parents[cur_node]:
                continue
            cur_max = max(cur_max, max_edges[cur_node, nxt_node])
            cur_min = min(cur_min, min_edges[cur_node, nxt_node])
        max_edges[parents[cur_node], cur_node] = cur_max
        min_edges[parents[cur_node], cur_node] = cur_min
    for cur_node in travel:
        mins = [cur_node]
        maxs = [cur_node]
        for nxt_node in tree[cur_node]:
            mins.append(min_edges[cur_node, nxt_node])
            maxs.append(max_edges[cur_node, nxt_node])
        mins = heapq.nsmallest(2, mins)
        maxs = heapq.nlargest(2, maxs)
        for nxt_node in tree[cur_node]:
            if nxt_node == parents[cur_node]:
                continue
            if min_edges[cur_node, nxt_node] == mins[0]:
                min_edges[nxt_node, cur_node] = mins[1]
            else:
                min_edges[nxt_node, cur_node] = mins[0]
            if max_edges[cur_node, nxt_node] == maxs[0]:
                max_edges[nxt_node, cur_node] = maxs[1]
            else:
                max_edges[nxt_node, cur_node] = maxs[0]
    for cur_node in range(n):
        edges = []
        max_left_r = -1
        for nxt_node in tree[cur_node]:
            (l, r) = (min_edges[cur_node, nxt_node], max_edges[cur_node, nxt_node])
            if l > cur_node:
                if r != n - 1:
                    edges.append((r, r + 1))
            else:
                if l != 0:
                    edges.append((l - 1, l))
                max_left_r = max(max_left_r, r)
        if max_left_r > cur_node and max_left_r != n - 1:
            edges.append((max_left_r, max_left_r + 1))
        if max_left_r < cur_node and 0 < cur_node < n - 1:
            edges.append((cur_node - 1, cur_node + 1))
        cost = sum((b - a for (a, b) in edges))
        print(cost, len(edges))
        for (a, b) in edges:
            print(a + 1, b + 1)
        print()
    return
if __name__ == '__main__':
    t = inp()
    for i in range(t):
        solution()

Solution (Python):
from sys import stdin
from heapq import nsmallest, nlargest

def read_tree():
    n = int(stdin.readline())
    tree = [[] for i in range(n)]
    for i in range(n - 1):
        (a, b) = map(int, stdin.readline().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)
    return tree

def solve(tree):
    n = len(tree)
    min_v = {}
    max_v = {}
    traversal = [0]
    prev = [None] * n
    prev[0] = 0
    processed = 0
    while processed < len(traversal):
        v = traversal[processed]
        processed += 1
        for u in tree[v]:
            if u == prev[v]:
                continue
            prev[u] = v
            traversal.append(u)
    for v in reversed(traversal):
        if v == prev[v]:
            continue
        curr_max = v
        curr_min = v
        for u in tree[v]:
            if u == prev[v]:
                continue
            curr_max = max(curr_max, max_v[v, u])
            curr_min = min(curr_min, min_v[v, u])
        max_v[prev[v], v] = curr_max
        min_v[prev[v], v] = curr_min
    for v in traversal:
        mins = [v]
        maxs = [v]
        for u in tree[v]:
            mins.append(min_v[v, u])
            maxs.append(max_v[v, u])
        mins = nsmallest(2, mins)
        maxs = nlargest(2, maxs)
        for u in tree[v]:
            if u == prev[v]:
                continue
            if min_v[v, u] == mins[0]:
                min_v[u, v] = mins[1]
            else:
                min_v[u, v] = mins[0]
            if max_v[v, u] == maxs[0]:
                max_v[u, v] = maxs[1]
            else:
                max_v[u, v] = maxs[0]
    for v in range(n):
        edges = []
        max_left_r = -1
        for u in tree[v]:
            (l, r) = (min_v[v, u], max_v[v, u])
            if l > v:
                if r != n - 1:
                    edges.append((r, r + 1))
            else:
                if l != 0:
                    edges.append((l - 1, l))
                max_left_r = max(max_left_r, r)
        if max_left_r > v and max_left_r != n - 1:
            edges.append((max_left_r, max_left_r + 1))
        if max_left_r < v and 0 < v < n - 1:
            edges.append((v - 1, v + 1))
        cost = sum((b - a for (a, b) in edges))
        assert len(edges) == len(tree[v]) - 1 or not tree[v], (v, tree[v], edges)
        print(cost, len(edges))
        for (a, b) in edges:
            print(a + 1, b + 1)
        print()
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    solve(read_tree())