Doremy's Experimental Tree (Codeforces 1764F)
Tags: Others, dsu

Doremy has an edge-weighted tree with $$$n$$$ vertices whose weights are integers between $$$1$$$ and $$$10^9$$$. She does $$$\frac{n(n+1)}{2}$$$ experiments on it.In each experiment, Doremy chooses vertices $$$i$$$ and $$$j$$$ such that $$$j \leq i$$$ and connects them directly with an edge with weight $$$1$$$. Then, there is exactly one cycle (or self-loop when $$$i=j$$$) in the graph. Doremy defines $$$f(i,j)$$$ as the sum of lengths of shortest paths from every vertex to the cycle.Formally, let $$$\mathrm{dis}_{i,j}(x,y)$$$ be the length of the shortest path between vertex $$$x$$$ and $$$y$$$ when the edge $$$(i,j)$$$ of weight $$$1$$$ is added, and $$$S_{i,j}$$$ be the set of vertices that are on the cycle when edge $$$(i,j)$$$ is added. Then,$$$$$$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$$$$$Doremy writes down all values of $$$f(i,j)$$$ such that $$$1 \leq j \leq i \leq n$$$, then goes to sleep. However, after waking up, she finds that the tree has gone missing. Fortunately, the values of $$$f(i,j)$$$ are still in her notebook, and she knows which $$$i$$$ and $$$j$$$ they belong to. Given the values of $$$f(i,j)$$$, can you help her restore the tree?It is guaranteed that at least one suitable tree exists.

Input: The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of vertices in the tree.The following $$$n$$$ lines contain a lower-triangular matrix with $$$i$$$ integers on the $$$i$$$-th line; the $$$j$$$-th integer on the $$$i$$$-th line is $$$f(i,j)$$$ ($$$0 \le f(i,j) \le 2\cdot 10^{15}$$$).It is guaranteed that there exists a tree whose weights are integers between $$$1$$$ and $$$10^9$$$ such that the values of $$$f(i,j)$$$ of the tree match those given in the input.

Output: Print $$$n-1$$$ lines describing the tree. In the $$$i$$$-th line of the output, output three integers $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$1 \le w_i \le 10^9$$$), representing an edge $$$(u_i,v_i)$$$ whose weight is $$$w_i$$$.If there are multiple answers, you may output any.All edges must form a tree and all values of $$$f(i,j)$$$ must match those given in the input.

Note: In the first test case, the picture below, from left to right, from top to bottom, shows the graph when pairs $$$(1,1)$$$, $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,2)$$$, $$$(2,3)$$$, $$$(3,3)$$$ are connected with an edge, respectively. The nodes colored yellow are on the cycle.

Sample Inputs:
3
7
3 5
0 2 8

9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748217280 1748217069 5741194692 749972427 10439821163
2377558289 2377559274 2377559063 6370536686 1379314421 5028071980 8866466178
1746983932 1746984917 1746984706 5739962329 748740064 10438588800 5026839617 10448447704
2341942133 2341943118 2341942907 6334920530 1343698265 4992455824 8830850022 4991223461 9115779270

Sample Outputs:
2 3 3
1 2 2

1 2 985
2 3 211
2 4 998244353
2 5 998244853
4 6 671232353
6 8 1232363
4 7 356561356
7 9 35616156

Solution (Python):
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
from sys import stdin
input = lambda : stdin.readline()[:-1]

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
solve()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return self.group

    def all_group_members(self):
        dic = {r: [] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic

    def __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
T = 1
for t in range(1, T + 1):
    solve()

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return self.group

    def all_group_members(self):
        dic = {r: [] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic

    def __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
T = 1
for t in range(1, T + 1):
    solve()