ユニークビジョンプログラミングコンテスト2025 クリスマス（AtCoder Beginner Contest 437）C,E,F,G問題メモ

def solve(n, reindeer):
    pw = []
    w_total = 0
    for w, p in reindeer:
        pw.append(p + w)
        w_total += w
    pw.sort(reverse=True)
    tmp = 0
    for i in range(n):
        tmp += pw[i]
        if tmp >= w_total:
            return n - i - 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    reindeer = [list(map(int, input().split())) for _ in range(n)]
    ans = solve(n, reindeer)
    print(ans)

import sys
from dataclasses import dataclass

sys.setrecursionlimit(300_003)


@dataclass
class Node:
    children: dict
    indexes: list


def solve(n, queries):
    root = Node({}, [])
    nodes = [root]
    for i in range(n):
        x, y = queries[i]
        i += 1
        node = nodes[x]
        if y in node.children:
            new_node = node.children[y]
        else:
            new_node = Node({}, [])
            node.children[y] = new_node
        new_node.indexes.append(i)
        nodes.append(new_node)

    ans = []

    def restore(node):
        ans.extend(node.indexes)
        for y in sorted(node.children):
            restore(node.children[y])

    restore(root)
    return ans


n = int(input())
queries = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, queries)
print(*ans)

from atcoder.segtree import SegTree


def solve(n, q, trees, queries):
    init = []
    for x, y in trees:
        init.append((x + y, x + y, x - y, x - y))

    def merge(a, b):
        return (max(a[0], b[0]), min(a[1], b[1]), max(a[2], b[2]), min(a[3], b[3]))

    INF = 1 << 60
    e = (-INF, INF, -INF, INF)

    sgt = SegTree(merge, e, init)

    buf = []
    for query in queries:
        if query[0] == 1:
            _, i, x, y = query
            sgt.set(i - 1, (x + y, x + y, x - y, x - y))
        else:
            _, l, r, x, y = query
            ur, dl, dr, ul = sgt.prod(l - 1, r)
            ans = max(
                ur - (x + y),
                (x + y) - dl,
                dr - (x - y),
                (x - y) - ul,
            )
            buf.append(ans)
    return buf


n, q = list(map(int, input().split()))
trees = [list(map(int, input().split())) for _ in range(n)]
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, trees, queries)
print('\n'.join(map(str, ans)))

グラフの構造上、最大流において同じ $u,v$ 間の複数の $(c_1,c_2)$ の組で、 $V_{u,c_1}→V_{v,c_2}$ に流れてしまい、$(c_1,c_2)$ が一意に決まらない可能性がありそうに思えてしまう。

 ,→(u,R)  (v,R)--,   （わかりやすくu,vのみ描画しているが、他の頂点もある場合）
S-→(u,G)＊(v,G)---T    (u,R)→(v,G) にも (u,G)→(v,B) にも
 `→(u,B)  (v,B)--'     流れてしまうようなことがあるのでは？

たしかに一般の二部グラフで同じような辺の張り方をするとそうなのだが、今回は二部グラフの中でも木なので、 最大流で $N-1$ の流量が流せたなら、各 $u,v$ につき $(c_1,c_2)$ は必ず唯一に決まると言える。

なぜか。

まぁ、「元の木の1本の辺に流量1ずつ対応させないと、全体の流量の整合が取れなくなる」で 直感的に納得できるならそれでよいのだが。

葉から考えればよい。木には葉が必ずある。
葉 $u$ をグループAだとする。（Bでも対称的に考えれば同じことが言える）

葉 $u$ では $\displaystyle \sum_{c_1} A_{u,c_1}=1$ なので、全色を合計して $S$ から流量 $1$ だけ水が流れている。
その水はこの後、相手 $v$ との間に流れる。ここでも当然、流量は全色を通して $1$ である。言い換えると、以下が言える。

• $\displaystyle \sum_{c_1}\sum_{c_2}（V_{u,c_1}→V_{v,c_2} に流れた量）=1$

よって、この辺に対する $(c_1,c_2)$ は一意に決まる。

すると、最大流用のグラフからこの辺 $(u,v)$ に関する辺を取り除き、$A_{v,c_2}$ も $1$ 減らした後のグラフでも 再帰的に同じ議論ができる。 これを繰り返し、全ての辺について $(c_1,c_2)$ は一意に決まる。

公式Editorialの写経となるが。

「初期状態で操作できる辺が必ず1本は存在する」ことを示せれば、分割後の木でも再帰的に同じことが言え、 全ての辺について操作可能であることが示せる。

背理法で示す。全ての辺について、その辺を消すときの希望の色が、初期の色の組 $(c_u,c_v)$ とは異なると仮定する。

適当な頂点を根とし、根から最も遠い頂点（の1つ）を考える。

      :
     (q)
     / \
   (p) (r)
  ／|＼
(v)(w)(x)

$v$ は葉なので、辺 $(p,v)$ を消すときの希望の色は、初期の色 $c_v$ に決まっている。
よって、$(p,v)$ に希望の色で操作できない場合、$p$ 側の初期の色 $c_p$ が希望の色でないということになる。

このことは $p$ の $v$ 以外の子 $w,x$ に対しても言える。どの子との辺に対しても、$c_p$ は希望の色ではない。

しかし、少なくとも $p$ から出る辺の1つは $c_p$ で操作するはずである。 （そのようにマッチングできるか試し、成功しているので）
それは $q$ との辺しか残されていない。

すると、今度は $p,q$ 間について似たようなことがいえ、辺 $(p,q)$ にとって $c_q$ が希望の色ではないことになる。

これを繰り返すと根まで波及する。しかし、根は親が無いため、$c_{root}$ で操作する辺が存在しないということになってしまう。

これは、二部マッチングが成功しているという事実に矛盾する。

from collections import deque
from typing import Tuple, List


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]

    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])

    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow

    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges


def dfs(n, links):
    depths = [-1] * n
    q = [0]
    depths[0] = 0
    while q:
        u = q.pop()
        dv = depths[u] + 1
        for v in links[u]:
            if depths[v] != -1:
                continue
            depths[v] = dv
            q.append(v)
    return depths


def solve(n, colors, edges):
    edges = [(u - 1, v - 1) for u, v in edges]
    links = [[] for _ in range(n)]
    for u, v in edges:
        links[u].append(v)
        links[v].append(u)
    depths = dfs(n, links)
    s = n * 3
    t = s + 1
    dnc = Dinic(3 * n + 2)

    for u in range(n):
        c = 'RGB'.index(colors[u])
        deg = len(links[u])
        d, m = divmod(deg, 3)
        cnt = [d, d, d]
        for i in range(c, c + m):
            cnt[i % 3] += 1

        if depths[u] % 2 == 0:
            for i in range(3):
                dnc.add_link(s, u * 3 + i, cnt[i])
            for v in links[u]:
                for i in range(3):
                    for j in range(3):
                        if i != j:
                            dnc.add_link(u * 3 + i, v * 3 + j, 1)
        else:
            for i in range(3):
                dnc.add_link(u * 3 + i, t, cnt[i])

    mf = dnc.max_flow(s, t)
    if mf < n - 1:
        return None

    edge_mapping = {(u, v): i for i, (u, v) in enumerate(edges)}
    edge_colors = [None] * (n - 1)
    for u in range(n):
        if depths[u] % 2 == 1:
            continue
        for i in range(3):
            for cap, to, rev, orig in dnc.links[u * 3 + i]:
                if cap == 0 and orig == 1:
                    v, j = divmod(to, 3)
                    if (u, v) in edge_mapping:
                        ei = edge_mapping[u, v]
                        edge_colors[ei] = (i, j)
                    else:
                        ei = edge_mapping[v, u]
                        edge_colors[ei] = (j, i)

    current_colors = ['RGB'.index(c) for c in colors]
    used = [False] * n
    ans = []
    for _ in range(n - 1):
        for ei in range(n - 1):
            if used[ei]:
                continue
            u, v = edges[ei]
            i, j = edge_colors[ei]
            if current_colors[u] == i and current_colors[v] == j:
                ans.append(ei + 1)
                used[ei] = True
                current_colors[u] = (current_colors[u] + 1) % 3
                current_colors[v] = (current_colors[v] + 1) % 3
                break
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    colors = input()
    edges = [list(map(int, input().split())) for _ in range(n - 1)]
    ans = solve(n, colors, edges)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(*ans)