AtCoder Regular Contest 179 B,D問題メモ

m, n = map(int, input().split())
xxx = list(map(int, input().split()))
xxx = [x - 1 for x in xxx]
MOD = 998244353

# i を置くことで条件が満たされる数字
fulfill = [0] * m
for i, x in enumerate(xxx):
    fulfill[x] |= 1 << i

pow2m = 1 << m
dp = [0] * pow2m
dp[-1] = 1

for _ in range(n):
    ndp = [0] * pow2m

    for bitset in range(1, pow2m):
        k = bitset
        while k:
            lsb = k & -k
            k ^= lsb
            i = lsb.bit_length() - 1
            ndp[bitset ^ lsb | fulfill[i]] += dp[bitset]

    for i in range(pow2m):
        ndp[i] %= MOD

    dp = ndp

ans = sum(dp) % MOD
print(ans)

from dataclasses import dataclass
from typing import List, Callable, TypeVar

T = TypeVar('T')
U = TypeVar('U')


@dataclass
class RerootingEdge:
    src: int
    tgt: int
    value: U


class Rerooting:
    """
    抽象化 全方位木DP
    ・r = 1,2,...,N について、頂点 r を根とした木DPの結果（DP[r]）を求める。
    ・merge 演算に逆演算が成り立たない場合に対応
    ・頂点に対して値が決められている場合、辺に対して値が決められている場合（あるいは両方）のいずれにも対応

    【使い方】
    ① __init__()に示された関数を定義する
    ② add_edge()にてN-1本の辺を与える。u→v と v→u で2回呼んで双方向で与える。
    ③ solve()

    【apply, merge 関数で処理すべき内容】
       (u)      ans[v] には、"v 自身の値は未反映の" v 以下の部分木に対するDP結果が入る。（その方が定義する関数の数を減らせるため）
      ／|＼      （※ たとえば「ans[i] = i 以下の部分木の頂点数」とした場合、ans[v] には v 自身は加算されていない）
    (v)(w)(x)   ans[u] を求める際に呼ばれる apply(ans[v]) 内で、v についての情報を加算する。
                apply では↑と同時に、辺をv→uとたどる際に何らかの処理が行われる場合はそれも反映する。頂点 u の値の反映は行わない。
                merge は、[ unit, apply(ans[v]), apply(ans[w]), apply(ans[x]) ] を左から2つずつ累積的に合成していく処理を行う。
                全てマージされた結果が、ans[u] となる。
    """

    def __init__(self,
                 n: int,
                 leaf_factory: Callable[[], T],  # 1回目のDFSで葉に適用する値
                 unit_factory: Callable[[], T],  # 単位元
                 merge: Callable[[T, T], T],  # 演算
                 apply: Callable[[T, RerootingEdge], T],  # [子の値, 親→子への辺] から、親に伝える情報を計算
                 ) -> None:
        self.n: int = n
        self.links: List[List[RerootingEdge]] = [[] for _ in range(n)]
        self.leaf = leaf_factory
        self.unit = unit_factory
        self.merge = merge
        self.apply = apply

    def add_edge(self, s, t, value) -> None:
        self.links[s].append(RerootingEdge(src=s, tgt=t, value=value))

    def solve(self) -> List[T]:
        links = self.links
        status = [0] * self.n

        leaf = self.leaf
        unit = self.unit
        merge = self.merge
        apply = self.apply

        # 1回目のDFSで、自身の子のapply済み結果の左からの累積和
        acc_left: List[List[T]] = [[unit()] for _ in range(self.n)]
        # 1回目のDFSで、自身の子のapply済み結果の右からの累積和
        acc_right: List[List[T]] = [[unit()] for _ in range(self.n)]

        # 最終結果（1回目のDFSでは自身のsubtreeのみの結果が入る）
        ans: List[T] = [unit() for _ in range(self.n)]
        # 親に向かう辺
        parents: List[RerootingEdge | None] = [None for _ in range(self.n)]
        # 2回目のDFSで、親から伝播される値（apply済）
        from_parent: List[T] = [unit() for _ in range(self.n)]

        q = [0]
        while q:
            v = q[-1]
            if status[v] == 0:
                status[v] = 1

                # 親頂点をリンクリストから除く
                children_links = []
                for e in links[v]:
                    if status[e.tgt] == 0:
                        children_links.append(e)
                    else:
                        parents[v] = e
                links[v] = children_links

                for e in links[v]:
                    q.append(e.tgt)
            else:
                q.pop()

                if len(links[v]) == 0:
                    ans[v] = leaf()

                else:
                    acl = acc_left[v]

                    for e in links[v]:
                        acl.append(apply(ans[e.tgt], e))

                    acr = acc_right[v]
                    for i in range(len(acl) - 1, 0, -1):
                        acr.append(merge(acl[i], acr[-1]))
                    acr.reverse()

                    for i in range(1, len(acl)):
                        acl[i] = merge(acl[i - 1], acl[i])

                    ans[v] = acl[-1]

                status[v] = 2

        q = [0]
        while q:
            v = q.pop()
            fp = from_parent[v]
            ans[v] = merge(ans[v], fp)

            acl = acc_left[v]
            acr = acc_right[v]
            for li, e in enumerate(links[v]):
                pe = parents[e.tgt]
                tgt_data = merge(fp, merge(acl[li], acr[li + 1]))
                from_parent[e.tgt] = apply(tgt_data, pe)
                q.append(e.tgt)

        return ans


n = int(input())

# 1: その部分木内でゲートを使った場合の最小コスト
# 2: 部分木の頂点数（v そのものの頂点の +1 は未反映）
# 3: 部分木の最大深さ（v そのものの深さの +1 は未反映）
# 4: 最後に訪れる枝として選ぶときの、1 から省略できるコスト差分
leaf_factory = lambda: (0, 0, 0, 0)
unit_factory = lambda: (0, 0, 0, 0)


def merge(a, b):
    a1, a2, a3, a4 = a
    b1, b2, b3, b4 = b
    return (a1 + b1, a2 + b2, max(a3, b3), max(a4, b4))


def apply(p, e):
    p1, p2, p3, p4 = p
    p2 += 1
    p3 += 1
    best_cost = min(p1 + 2, p2 * 2 - p3)
    last_cost = min(p1 - p4 + 1, p2 * 2 - p3)
    return (best_cost, p2, p3, best_cost - last_cost)


rrt = Rerooting(n, leaf_factory, unit_factory, merge, apply)

for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    rrt.add_edge(u, v, 0)
    rrt.add_edge(v, u, 0)

result = rrt.solve()

ans = 1 << 60
for p1, _, _, p4 in result:
    ans = min(ans, p1 - p4)

print(ans)