AtCoder Beginner Contest 447 E,F,G問題メモ

from atcoder.dsu import DSU


def solve(n, m, edges):
    MOD = 998244353
    uft = DSU(n)
    merged_count = 0
    ans = 0
    i = m - 1
    while merged_count < n - 2:
        u, v = edges[i]
        u -= 1
        v -= 1
        if not uft.same(u, v):
            merged_count += 1
        uft.merge(u, v)
        i -= 1
    for j in range(i, -1, -1):
        u, v = edges[j]
        u -= 1
        v -= 1
        if uft.same(u, v):
            continue
        ans += pow(2, j + 1, MOD)

    ans %= MOD
    return ans


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

def solve(n, edges):
    links = [[] for _ in range(n)]
    for a, b in edges:
        a -= 1
        b -= 1
        links[a].append(b)
        links[b].append(a)
    degrees = [len(links[i]) for i in range(n)]

    dp = [-1] * n
    q = [0]
    ans = 1
    while q:
        u = q[-1]
        if dp[u] == -1:
            dp[u] = -2
            for v in links[u]:
                if dp[v] == -1:
                    q.append(v)
            continue
        q.pop()

        if degrees[u] < 3:
            dp[u] = 0
            continue
        if degrees[u] == 3:
            dp[u] = 1
            ans = max(ans, 1)
            for v in links[u]:
                if dp[v] > 0:
                    ans = max(ans, dp[v] + 1)
            continue
        mx1 = 0
        mx2 = 0
        dp[u] = 1
        for v in links[u]:
            if dp[v] > 0:
                dp[u] = max(dp[u], dp[v] + 1)
                if mx1 < dp[v]:
                    mx2 = mx1
                    mx1 = dp[v]
                elif mx2 < dp[v]:
                    mx2 = dp[v]
        ans = max(ans, mx1 + mx2 + 1)
    return ans


q = int(input())
for _ in range(q):
    n = int(input())
    edges = [list(map(int, input().split())) for _ in range(n - 1)]
    ans = solve(n, edges)
    print(ans)

from collections import defaultdict
from pprint import pprint

from atcoder.segtree import SegTree


def solve(n, problems):
    kkk, aaa = zip(*problems)

    # k_pos[k] := kkk[i]=k である i のリスト
    k_pos = defaultdict(list)
    # left_single[x] := ((a1,k1),(a2,k2),(a3,k3),(a4,k4))  i<x を満たす i のうち、kkk[i] が相異なる中での aaa[i] の上位4件（降順）
    left_single = []
    # left_triple[x] := i<j<x かつ kkk[i],kkk[j],kkk[x] が相異なる (i,j,x) のうち、aaa[i]+aaa[j]+aaa[x] の最大値
    left_triple = []
    # recalculate[k] := left_triple を求める時、kkk[i]=k または kkk[j]=k だったような x のリスト
    recalculate = defaultdict(list)
    top_n_single = 4

    def get_double(single, k1, k2=-2, register_recalc=False):
        result = 0
        count = 0
        for j in range(top_n_single):
            if single[j][1] != k1 and single[j][1] != k2:
                result += single[j][0]
                count += 1
                if register_recalc:
                    recalculate[single[j][1]].append(i)
                if count >= 2:
                    break
        return result

    def update_top_n(top_items, a, k, top_n):
        for i in range(top_n):
            if top_items[i][1] == k:
                top_items[i] = (max(top_items[i][0], a), k)
                top_items.sort(reverse=True)
                break
        else:
            top_items.append((a, k))
            top_items.sort(reverse=True)
            top_items.pop()

    NINF = -1 << 60
    single = [(NINF, -1)] * top_n_single
    for i in range(n):
        k = kkk[i]
        a = aaa[i]
        k_pos[k].append(i)
        left_single.append(tuple(single))

        triple = a + get_double(single, k, register_recalc=True)
        left_triple.append(triple)

        update_top_n(single, a, k, top_n_single)

    right_single = []
    single = [(NINF, -1)] * top_n_single
    for i in range(n - 1, -1, -1):
        k = kkk[i]
        a = aaa[i]
        update_top_n(single, a, k, top_n_single)
        right_single.append(tuple(single))
    right_single.reverse()

    # pprint(f'{left_single=}')
    # pprint(f'{left_triple=}')
    # pprint(f'{recalculate=}')
    # pprint(f'{right_single=}')

    # セグ木
    # [(a1,k1),(a2,k2),(a3,k3),(a4,k4)]
    # k が異なる中で、triple の上位4件（降順保証, 存在しなければ (NINF,-1)）
    top_n_triple = 4

    def merge(a, b):
        i = 0
        j = 0
        result = []
        used = []
        while len(result) < top_n_triple:
            while i < top_n_triple and a[i][1] in used:
                i += 1
            while j < top_n_triple and b[j][1] in used:
                j += 1
            if i >= top_n_triple and j >= top_n_triple:
                result.append((NINF, -1))
                continue
            if i >= top_n_triple:
                result.append(b[j])
                used.append(b[j][1])
                j += 1
                continue
            if j >= top_n_triple:
                result.append(a[i])
                used.append(a[i][1])
                i += 1
                continue
            if a[i][1] == b[j][1]:
                result.append(max(a[i], b[j]))
                used.append(a[i][1])
                i += 1
                j += 1
            elif a[i][0] >= b[j][0]:
                result.append(a[i])
                used.append(a[i][1])
                i += 1
            else:
                result.append(b[j])
                used.append(b[j][1])
                j += 1
        return result

    init = [[(left_triple[i], kkk[i]), (NINF, -1), (NINF, -1), (NINF, -1)] for i in range(n)]
    sgt = SegTree(merge, [(NINF, -1)] * 4, init)

    ans = NINF
    for c, pos in k_pos.items():
        for i in recalculate[c]:
            k = kkk[i]
            single = left_single[i]
            triple = aaa[i]
            count = 0
            for j in range(top_n_single):
                if single[j][1] != c and single[j][1] != k:
                    triple += single[j][0]
                    count += 1
                    if count >= 2:
                        break
            sgt.set(i, [(triple, k), (NINF, -1), (NINF, -1), (NINF, -1)])

        for i in pos:
            left = sgt.prod(0, i)
            right = right_single[i]
            a = aaa[i]
            for s1, k1 in left:
                if k1 == c:
                    continue
                tmp = s1 + a
                count = 0
                for s2, k2 in right:
                    if k2 == k1 or k2 == c:
                        continue
                    tmp += s2
                    count += 1
                    if count >= 2:
                        break
                ans = max(ans, tmp)

        for i in recalculate[c]:
            sgt.set(i, init[i])

    if ans < 0:
        return -1
    return ans


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

</python>

++++

==== 解法2 ====

頭の良い乱択解法。Color Coding が使える。

  * [[https://atcoder.jp/contests/abc447/editorial/16740|解説 - AtCoder Beginner Contest 447]]

そもそもこの問題は、$1,2,3,4$ 番目、$3,4,5,6$ 番目で被ってはダメという、4要素にわたる重複禁止制約がきつい。
（4つめを選ぶとき、その前3つで選択したジャンルを覚えておかないといけない）

Color Coding を上手く使うと、これを「$1,2$、$3,4$、$5,6$ のそれぞれで被ってはダメ」という、2つずつの制約に分離できる。

ジャンルを2色 $(0,1)$ に色分けし、
「$1,2,5,6$ は色 $0$ から」「$3,4$ は色 $1$ から」選択する、という制約を課した問題を解くことにする。すると、

  * $3,4$ を選択するとき、$1,2$ を覚えておかなくても、自然とジャンルが被ることを阻止できる。
  * $5,6$ を選択するとき、$3,4$ を覚えておかなくても、自然とジャンルが被ることを阻止できる。

よって記憶すべき状態が非常に少なくなり、ある色分けに対し $O(N)$ で、その色分けにおける最適解が求められる。

真の最適解において $1,2,3,4,5,6$ 番目で選択する要素のジャンルに、
それぞれ適切に $(0,0,1,1,0,0)$ の色が割り当てられることが、正しく答えが求められる条件である。

色分けにおいて、ランダムに $(0,1)$ を $1/2$ で割り当てると、確率 $1/64$ 以上で正しくなる。\\
よりよい方法としては、$0$ を $2/3$、$1$ を $1/3$ で割り当てるようにすると、確率 $16/729$ 以上で正しくなる。

$500$ 回ほど繰り返すと、十分な精度（誤答率 $10^{-5}$ 以下）で、
1回は最適解の色が割り当てられることが期待できる。



++++ Python3 |

<sxh python>
import random


def solve(n, problems):
    # Color Coding
    kkk, aaa = zip(*problems)
    NINF = -1 << 60

    # kkk を 0～ジャンルの種類数 にノーマライズ
    kkk_values = sorted(set(kkk))
    mapping = {k: i for i, k in enumerate(kkk_values)}
    kkk = [mapping[k] for k in kkk]
    m = len(kkk_values)

    def update_top2(dp, k, a):
        if dp[0] == k:
            if dp[1] < a:
                dp[1] = a
        elif dp[1] < a:
            dp[2] = dp[1]
            dp[0] = k
            dp[1] = a
        elif dp[2] < a:
            dp[2] = a

    def trial():
        groups = random.choices((0, 0, 1), k=m)
        dp1 = [-1, NINF, NINF]
        dp2 = NINF
        dp3 = [-1, NINF, NINF]
        dp4 = NINF
        dp5 = [-1, NINF, NINF]
        dp6 = NINF
        for i in range(n):
            k = kkk[i]
            a = aaa[i]
            if groups[k] == 0:
                dp2 = max(dp2, (dp1[2] if dp1[0] == k else dp1[1]) + a)
                update_top2(dp1, k, a)
                dp6 = max(dp6, (dp5[2] if dp5[0] == k else dp5[1]) + a)
                update_top2(dp5, k, dp4 + a)
            else:
                dp4 = max(dp4, (dp3[2] if dp3[0] == k else dp3[1]) + a)
                update_top2(dp3, k, dp2 + a)
        return dp6

    TRIAL_COUNT = 500
    ans = max(trial() for _ in range(TRIAL_COUNT))
    if ans < 0:
        return -1
    return ans


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