Jeremy Bearimy (Codeforces 1280C)
Tags: Greedy, trees

Welcome! Everything is fine.You have arrived in The Medium Place, the place between The Good Place and The Bad Place. You are assigned a task that will either make people happier or torture them for eternity.You have a list of $$$k$$$ pairs of people who have arrived in a new inhabited neighborhood. You need to assign each of the $$$2k$$$ people into one of the $$$2k$$$ houses. Each person will be the resident of exactly one house, and each house will have exactly one resident.Of course, in the neighborhood, it is possible to visit friends. There are $$$2k - 1$$$ roads, each of which connects two houses. It takes some time to traverse a road. We will specify the amount of time it takes in the input. The neighborhood is designed in such a way that from anyone's house, there is exactly one sequence of distinct roads you can take to any other house. In other words, the graph with the houses as vertices and the roads as edges is a tree.The truth is, these $$$k$$$ pairs of people are actually soulmates. We index them from $$$1$$$ to $$$k$$$. We denote by $$$f(i)$$$ the amount of time it takes for the $$$i$$$-th pair of soulmates to go to each other's houses.As we have said before, you will need to assign each of the $$$2k$$$ people into one of the $$$2k$$$ houses. You have two missions, one from the entities in The Good Place and one from the entities of The Bad Place. Here they are:  The first mission, from The Good Place, is to assign the people into the houses such that the sum of $$$f(i)$$$ over all pairs $$$i$$$ is minimized. Let's define this minimized sum as $$$G$$$. This makes sure that soulmates can easily and efficiently visit each other;  The second mission, from The Bad Place, is to assign the people into the houses such that the sum of $$$f(i)$$$ over all pairs $$$i$$$ is maximized. Let's define this maximized sum as $$$B$$$. This makes sure that soulmates will have a difficult time to visit each other. What are the values of $$$G$$$ and $$$B$$$?

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) denoting the number of test cases. The next lines contain descriptions of the test cases.The first line of each test case contains a single integer $$$k$$$ denoting the number of pairs of people ($$$1 \le k \le 10^5$$$). The next $$$2k - 1$$$ lines describe the roads; the $$$i$$$-th of them contains three space-separated integers $$$a_i, b_i, t_i$$$ which means that the $$$i$$$-th road connects the $$$a_i$$$-th and $$$b_i$$$-th houses with a road that takes $$$t_i$$$ units of time to traverse ($$$1 \le a_i, b_i \le 2k$$$, $$$a_i \neq b_i$$$, $$$1 \le t_i \le 10^6$$$). It is guaranteed that the given roads define a tree structure.It is guaranteed that the sum of the $$$k$$$ in a single file is at most $$$3 \cdot 10^5$$$.

Output: For each test case, output a single line containing two space-separated integers $$$G$$$ and $$$B$$$. 

Note: For the sample test case, we have a minimum sum equal to $$$G = 15$$$. One way this can be achieved is with the following assignment:  The first pair of people get assigned to houses $$$5$$$ and $$$6$$$, giving us $$$f(1) = 5$$$;  The second pair of people get assigned to houses $$$1$$$ and $$$4$$$, giving us $$$f(2) = 6$$$;  The third pair of people get assigned to houses $$$3$$$ and $$$2$$$, giving us $$$f(3) = 4$$$. Note that the sum of the $$$f(i)$$$ is $$$5 + 6 + 4 = 15$$$. We also have a maximum sum equal to $$$B = 33$$$. One way this can be achieved is with the following assignment:  The first pair of people get assigned to houses $$$1$$$ and $$$4$$$, giving us $$$f(1) = 6$$$;  The second pair of people get assigned to houses $$$6$$$ and $$$2$$$, giving us $$$f(2) = 14$$$;  The third pair of people get assigned to houses $$$3$$$ and $$$5$$$, giving us $$$f(3) = 13$$$. Note that the sum of the $$$f(i)$$$ is $$$6 + 14 + 13 = 33$$$. 

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

Sample Outputs:
15 33
6 6

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    p = [s]
    l = 0
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    e = []
    while len(p) ^ l:
        i = p[l]
        for (j, t) in G[i]:
            if not visit[j]:
                visit[j] = 1
                parent[j] = i
                p.append(j)
                e.append(t)
        l += 1
    return (p, parent, e)
q = int(input())
ans = []
for _ in range(q):
    k = int(input())
    n = 2 * k
    G = [[] for _ in range(n + 1)]
    g = 0
    for _ in range(n - 1):
        (a, b, t) = map(int, input().split())
        g += t
        G[a].append((b, t))
        G[b].append((a, t))
    (p, parent, e) = bfs(1)
    dp = [1] * (n + 1)
    b = 0
    while len(p) ^ 1:
        i = p.pop()
        t = e.pop()
        dpi = dp[i]
        if not dpi % 2:
            g -= t
        b += min(dpi, n - dpi) * t
        j = parent[i]
        dp[j] += dpi
    ans.append(' '.join(map(str, (g, b))))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for T in range(int(input())):
    k = int(input())
    counts = [0] * (2 * k + 1)
    adjacencies = [list() for i in range(2 * k + 1)]
    for _ in range(2 * k - 1):
        (a, b, weight) = map(int, input().split())
        counts[a] += 1
        counts[b] += 1
        adjacencies[a].append((b, weight))
        adjacencies[b].append((a, weight))
    parents = [0] * (2 * k + 1)
    weights = [0] * (2 * k + 1)
    root = 1
    parents[root] = root
    queue = [root]
    index = 0
    while index < len(queue):
        node = queue[index]
        for (child, weight) in adjacencies[node]:
            if parents[child] < 1:
                parents[child] = node
                weights[child] = weight
                queue.append(child)
        index += 1
    subtree_sizes = [1] * (2 * k + 1)
    maximum = minimum = 0
    for node in reversed(queue):
        subtree_sizes[parents[node]] += subtree_sizes[node]
        if subtree_sizes[node] & 1:
            minimum += weights[node]
        maximum += weights[node] * min(subtree_sizes[node], 2 * k - subtree_sizes[node])
    print(minimum, maximum)

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

def main():
    for _ in range(int(input())):
        n = 2 * int(input())
        path = [[] for _ in range(n)]
        cost = [[] for _ in range(n)]
        for _ in range(n - 1):
            (a1, b1, c) = map(int, input().split())
            path[a1 - 1].append(b1 - 1)
            path[b1 - 1].append(a1 - 1)
            cost[a1 - 1].append(float(c))
            cost[b1 - 1].append(float(c))
        (st, poi, visi) = ([0], [0] * n, [1] + [0] * (n - 1))
        (child, pt, G, B) = ([1] * n, 0, 0, 0)
        while len(st):
            (x, y) = (st[-1], path[st[-1]])
            if poi[x] != len(y) and visi[y[poi[x]]]:
                poi[x] += 1
            if poi[x] == len(y):
                st.pop()
                if len(st):
                    child[st[-1]] += child[x]
                    z = cost[st[-1]][poi[st[-1]] - 1]
                    pt -= z
                    if child[x] & 1:
                        G += z
            else:
                (i, j) = (y[poi[x]], cost[x][poi[x]])
                st.append(i)
                pt += j
                B += pt
                poi[x] += 1
                visi[i] = 1
        (st, poi, visi, x, diff) = ([0], [0] * n, [1] + [0] * (n - 1), 0, 0)
        while 1:
            (co, maxi, su, which) = (-1, 0, 1, -1)
            for (ind, j) in enumerate(path[x]):
                if visi[j]:
                    continue
                visi[j] = 1
                su += child[j]
                if child[j] > maxi:
                    (maxi, which) = (child[j], j)
                    co = cost[x][ind]
            if maxi - diff <= su - maxi:
                break
            B -= co * (2 * maxi - su - diff)
            diff += su - maxi
            x = which
        print(int(G), int(B))
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')
if __name__ == '__main__':
    main()