パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 406）F,G問題メモ

パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 406）

F - Compare Tree Weights

• $N$ 頂点の木 $T$ があり、辺 $i$ $(1\leq i\leq N-1)$ は頂点 $U_i$ と頂点 $V_i$ を結んでいます。
• また、各頂点には重みが定められており、最初、各頂点の重みはすべて $1$ です。
• $Q$ 個のクエリが与えられるので、順に処理してください。各クエリは次の $2$ 種類のいずれかです。
  • '1 x w' : 頂点 $x$ の重みを $w$ 増加させる。
  • '2 y' : 辺 $y$ を削除すると、$T$ は $2$ つの部分木（連結成分）に分かれる。それぞれの部分木に含まれる頂点の重みの総和をその部分木の重みとするとき、$2$ つの部分木の重みの差を出力する。

• $2$ 種類目のクエリについて、$T$ から任意の辺を $1$ つ選んで削除したとき、$T$ は必ず $2$ つの部分木に分かれることが証明できます。
• また、$2$ 種類目のクエリでは、実際に辺を削除しているわけではないことに注意してください。

• $2\leq N\leq 3\times 10^5$
• $1\leq U_i,V_i\leq N$
• $1\leq Q\leq 3\times 10^5$
• $1\leq x\leq N$
• $1\leq w\leq 1000$
• $1\leq y\leq N-1$
• 入力はすべて整数
• 与えられるグラフは木である。
• $2$ 種類目のクエリが少なくとも $1$ つ存在する。

各頂点に付き以下が分かれば、

• $S_v:=$（頂点 $1$ を根とした時の）頂点 $v$ の部分木の重み

辺 $(u,v)$ を削除したとき、親を $u$ とすると、以下のように計算できる。

• $v$ 側の重みは $S_v$
• $u$ 側の重みは $S_1-S_v$
• よってクエリ2の答えは、$|S_1-2S_v|$

クエリ1で頂点 $v$ の重みを $w$ 増やした時、$1～v$ 間を結ぶパス上の各頂点の $S_v$ が $w$ ずつ増加する。

HL分解すれば木のパスは $O(\log{N})$ 個のセグメントで表現できるので、 双対セグ木やFenwickTreeに載せておけば、$O(\log^2{N})$ で加算処理を行える。

• 【図解】木のパスに関するクエリは HL 分解！ その仕組みと実装を図で理解する｜Heavy-Light Decomposition #AtCoder - Qiita

よって、$O(N+Q\log^2{N})$ でおこなえる。

Python3

from atcoder.fenwicktree import FenwickTree


def heavy_light_decomposition(
        n: int,
        children: list[list[int]],
        root: int = 0
) -> tuple[list[list[int]], list[int], list[int]]:
    """
    ①--②--④--⑦--⑨  →  [[1,2,4,7,9], [10], [3,5,8], [6]]
     `--③--⑤-⑧ `-⑩
         `--⑥
    Heavy-path のリストに分解する。
    Heavy-path の並びは、（最も重い子を最初に訪れるような）オイラーツアーの訪問順となる。
    """
    parents = [-1] * n
    weights = [-1] * n
    q = [root]
    while q:
        u = q[-1]
        if weights[u] == -1:
            weights[u] = -2
            for v in children[u]:
                if parents[u] == v:
                    continue
                parents[v] = u
                q.append(v)
        else:
            q.pop()
            weights[u] = 1 + sum(weights[v] for v in children[u] if v != parents[u])

    q = [root]
    progress = [0] * n
    progress2 = [0] * n
    current_path = []
    result = [current_path]
    while q:
        u = q[-1]
        if progress[u] == 0:
            children[u].sort(key=weights.__getitem__, reverse=True)
            current_path.append(u)
        if progress[u] >= len(children[u]):
            q.pop()
            continue
        v = children[u][progress[u]]
        progress[u] += 1
        if v == parents[u]:
            continue
        progress2[u] += 1
        if progress2[u] >= 2:
            current_path = []
            result.append(current_path)
        q.append(v)

    return result, weights, parents


def solve(n, edges, q, queries):
    links = [[] for _ in range(n)]
    edges = [(u - 1, v - 1) for u, v in edges]
    for u, v in edges:
        links[u].append(v)
        links[v].append(u)
    hld_paths, weights, parents = heavy_light_decomposition(n, links)
    hld_order = []
    hld_index = [0] * n
    weights2 = [0] * n
    success = [-1] * n
    skip = [-1] * n
    i = 0
    for hld_path in hld_paths:
        hld_order.extend(hld_path)
        p = hld_index[parents[hld_path[0]]]
        for j, v in enumerate(hld_path, start=i):
            hld_index[v] = j
            weights2[j] = weights[v]
            success[j] = i
            skip[j] = p
        i += len(hld_path)
    skip[0] = -1

    fwt = FenwickTree(n + 1)
    prev = 0
    for i, w in enumerate(weights2):
        fwt.add(i, w - prev)
        prev = w
    ans = []
    total = n
    for query in queries:
        if query[0] == 1:
            x = query[1] - 1
            i = hld_index[x]
            w = query[2]
            while i != -1:
                fwt.add(success[i], w)
                fwt.add(i + 1, -w)
                i = skip[i]
            total += w
        else:
            y = query[1]
            u, v = edges[y - 1]
            if parents[v] == u:
                i = hld_index[v]
            else:
                i = hld_index[u]
            val_v = fwt.sum(0, i + 1)
            val_u = total - val_v
            ans.append(abs(val_u - val_v))
    return ans


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

G - Travelling Salesman Problem

• 数直線上にあなたと $N$ 人の商人がいます。商人には $1, 2, \ldots, N$ の番号が付けられています。
• はじめ、あなたは座標 $0$ におり、商人 $i$ は座標 $X_i$ にいます。また、各商人は品物を $1$ つずつ持っており、商人 $i$ が持っている品物を品物 $i$ と表記します。
• あなたの目的は、品物 $1, 2, \ldots, N$ をこの順に受け取ることです。
• あなたは、以下の $3$ つの操作を好きな順序で好きな回数繰り返すことができます。
  • 自分が $1$ 移動する。この操作にはコストが $C$ かかる。
  • 商人を $1$ 人選び、選んだ商人に $1$ 移動してもらう。この操作にはコストが $D$ かかる。
  • 商人を $1$ 人選び、選んだ商人を商人 $i$ とする。あなたと商人 $i$ のいる座標が一致しており、あなたが商人 $i$ から品物を受け取ったことがない場合、商人 $i$ から品物 $i$ を受け取る。そうでない場合、何もしない。この操作にはコストが $0$ かかる。

• 目的を達成するためにかかるコストの合計の最小値を求めてください。
• また、目的を達成するためにかかるコストの合計を最小化したときに各商人から品物を受け取る座標として考えられるもののうちのひとつを求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C, D \leq 10^5$
• $-10^5 \leq X_i \leq 10^5$
• 入力される値はすべて整数

最小値だけなら、まだ Slope Trick を知っていれば典型に当てはめやすいが、座標も合わせて答えなければならないのが難しい。

ひとまず、TLE/MLEは気にせず、素直なわかりやすい求め方を考える。

• $F_{i,j}:=i$ 個目の商品を座標 $j$ で受け取るまでにかかる最小コスト

直前にいた座標 $k$ を全探索すると、遷移は以下のようになる。

• $\displaystyle F_{i,j}=\min_{k}(F_{i-1,k}+|k-j| \times C + |X_i-j| \times D)$

ただしこのままでは $O(NX_{\max}^2)$ かかるのでダメ。

足されるのが絶対値付きの関数であることからもわかるように、 $F_{i,j}$ は「$j$ についての区分線形凸関数」となる。
区分線形凸関数は、SlopeTrickで遷移を高速化できる。

• slope trick (1) 解説編 | maspyのHP

遷移を2段階に分けて考える。

• ① $\displaystyle F'_{i,j}=\min_{k}(F_{i-1,k}+|k-j| \times C)$
• ② $\displaystyle F_{i,j}=F'_{i,j}+|X_i-j| \times D$

①はどのような意味を持つのか少し分かりづらい。
①は、「関数の傾きを $[-C,C]$ に制限する」という役割を持つ。

       \                           /
  ~-_↙ x                         /           x:傾きの変化点
     ~-_ ＼                      / ↘  _-~
傾き -C ~-_＼                   /   _-~傾き C
           ~-x--___            / _-~
                   ~~~x-------x-~

「傾きが $C$ より大きければ、$|k-j|$ 個離れた位置から 1あたり $C$ かけて移動してきた方がコストが安くなる」と考えればわかりやすい。

その上で、②で $X_i$ を中心に両側の傾きをそれぞれ $D$ ずつ増やすと、SlopeTrick上での遷移が完了する。

で、最小値だけなら $F_{i,j}$ を適切に更新していくだけでよいのだが、 座標の復元には、$F_{N,*}$ の最小値を取る箇所から $F_{0,0}$ まで、遷移を逆にたどる必要がある。
最後になるまで、途中の $i$ でどの $j$ にいるのが最適かは確定しない。

N=6 C=6 D=8
2 -1 5 -2 -2 2

     j   -6   -5   -4   -3   -2   -1    0    1    2    3    4    5    6
       [ ∞,  ∞,  ∞,  ∞,  ∞,  ∞,   0,  ∞,  ∞,  ∞,  ∞,  ∞,  ∞]
                                        ￪
i=1 ① [ 36,  30,  24,  18,  12,   6,   0,   6,  12,  18,  24,  30,  36]
    ② [100,  86,  72,  58,  44,  30,  16,  14,  12,  26,  40,  54,  68]
                                   ,----'
i=2 ① [ 52,  46,  40,  34,  28,  22,  16,  14,  12,  18,  24,  30,  36]
    ② [ 92,  78,  64,  50,  36,  22,  24,  30,  36,  50,  64,  78,  92]
                                   |
i=3 ① [ 52,  46,  40,  34,  28,  22,  24,  30,  36,  42,  48,  54,  60]
    ② [140, 126, 112,  98,  84,  70,  64,  62,  60,  58,  56,  54,  68]
                              ,----'
i=4 ① [100,  94,  88,  82,  76,  70,  64,  62,  60,  58,  56,  54,  60]
    ② [132, 118, 104,  90,  76,  78,  80,  86,  92,  98, 104, 110, 124]
                              |
i=5 ① [100,  94,  88,  82,  76,  78,  80,  86,  92,  98, 104, 110, 116]
    ② [132, 118, 104,  90,  76,  86,  96, 110, 124, 138, 152, 166, 180]
                              `------------------,
i=6 ① [100,  94,  88,  82,  76,  82,  88,  94, 100, 106, 112, 118, 124]
    ② [164, 150, 136, 122, 108, 106, 104, 102, 100, 114, 128, 142, 156]
                                                BEST

仮に、上図のような $F_{i,j}$ の途中段階を全て保存しておければ、 「$F_{6,2}=100$ となるためには $i=5$ ではどの $j$ から遷移してきたか、$i=4$ では、$i=3$ では、、、」 と遡って調べていけるが、当然、これを全て持つわけにはいかない。

ところで、②の更新では各 $j$ に値が加算されるのみで特に $j$ 自身は動かない（遷移先 $j$ の遷移元は $j$ のみ）。
$j$ が動く（遷移先 $j$ に $j$ 以外からも遷移してくる）のは①の更新のみである。
で、$i$ から $i+1$ への①による更新は、左から以下の3区間に分けられる。

• a) 傾きが $-C$ 未満のため、$-C$ に揃えられた区間
• b) 傾きが $-C$ 以上 $C$ 以下のため、値が変わらない区間
• c) 傾きが $C$ より大きいため、$C$ に揃えられた区間

     j   -6   -5   -4   -3   -2   -1    0    1    2    3    4    5    6
i=2 ② [ 92,  78,  64,  50,  36,| 22,  24,  30,  36,| 50,  64,  78,  92]
                    a)          |         b)        |         c)
i=3 ① [ 52,  46,  40,  34,  28,| 22,  24,  30,  36,| 42,  48,  54,  60]

上例のように a),b),c) が分けられるとき、下段の各 $j$ に対する、遷移元となる上段の $j$ は、以下のようになっている。

     j   -6   -5   -4   -3   -2 | -1    0    1    2 |  3    4    5    6
遷移元 [ -1,  -1,  -1,  -1,  -1,| -1,   0,   1,   2,|  2,   2,   2,   2]

つまり、最も近い b) 内の $j$ となる。
よって、各 $i→i+1$ の①の更新における b) の両端座標さえ記録しておけば、 $F_{N,j}$ が最小値となる $j$ から遡りながらclipすることで、受け取る座標の復元が可能となる。

どのようなデータ構造で上記の処理を実現するかという点も、悩ましい。

SlopeTrickは、「傾き $0$ を中心に両側の変化点の $x$ 座標を HeapQueue 2本で管理する」という実装もあるが、 今回は「変化点の両端から傾きを $C$ に揃える」という操作がある。これはHeapQueueでは奥の方にある要素なので取り出しづらい。

• $s$: (傾きの変化点, 変化差分) を値に持つSortedListまたはSortedDict
• $v$: ↑の中で最も左側の変化点における暫定コスト
• $left[i]$: $i$ 番目の処理後の b) の左端index
• $right[i]$: $i$ 番目の処理後の b) の右端index

を持って更新していけばよい。

この問題では、両端無限遠点の傾きは①の後では $-C,C$、②の後では $-(C+D),C+D$ に揃えられるので、傾きの絶対値は敢えて持たなくてもよい。

更新もやや重く、境界あたりをちゃんと実装するのが難しい。
①の時、元の傾きが $-C,C$ ちょうどになる場合は、変化点ではなくなるので $s$ から削除はするが、b) の範囲内ではあるのでleft,rightには登録する、などでハマった。

SortedDictへの値の追加・削除・参照がそれぞれ $O(\log{要素数})$ として、 要素数は②でクエリに付き1個ずつ追加されるのみなので、全体で $O(N \log{N})$ でできる。

Python3

from sortedcontainers import SortedDict


def solve(n, c, d, xxx):
    INF = 1 << 20
    sd = SortedDict()
    sd[0] = 2 * (c + d)
    left_val = 0
    left = []
    right = []
    for x in xxx:
        ls = -(c + d)
        delete_keys = []
        prev = -INF
        for p, ch in sd.items():
            if prev != -INF:
                left_val += ls * (p - prev)

            if ls == -c:
                left.append(prev)
                break

            prev = p

            ls += ch
            if ls > -c:
                left.append(p)
                sd[p] = ls - (-c)
                break
            delete_keys.append(p)

        rs = c + d
        for p, ch in reversed(sd.items()):
            rs -= ch
            if rs <= c:
                right.append(p)
                if rs == c:
                    delete_keys.append(p)
                else:
                    sd[p] = c - rs
                break
            delete_keys.append(p)

        for p in delete_keys:
            del sd[p]

        mi, _ = sd.peekitem(0)
        if mi > x:
            sd[x] = d * 2
            left_val += c * (mi - x)
        elif x in sd:
            sd[x] += d * 2
            left_val += d * (x - mi)
        else:
            sd[x] = d * 2
            left_val += d * (x - mi)

    changes = sd.items()
    cost = left_val
    prev = changes[0][0]
    ls = -(c + d) + changes[0][1]
    for p, ch in changes[1:]:
        if ls >= 0:
            break
        cost += ls * (p - prev)
        ls += ch
        prev = p
    pos = [prev]
    for i in range(n - 1, 0, -1):
        prev = max(left[i], min(right[i], prev))
        pos.append(prev)
    pos.reverse()
    return cost, pos


n, c, d = map(int, input().split())
xxx = list(map(int, input().split()))
ans = naive(n, c, d, xxx)
cost, pos = solve(n, c, d, xxx)
print(cost)
print(*pos)