Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）E,G 問題メモ

n, m = map(int, input().split())
s = input()
t = input()
state = {-1}
for c in s:
    next_state = set()
    if m - 1 in state:
        for i in range(m):
            if c == t[i]:
                next_state.add(i)
    else:
        for i in state:
            if c == t[i + 1]:
                next_state.add(i + 1)
    if t[0] == c:
        next_state.add(0)
    state = next_state

    if len(state) == 0:
        break

if m - 1 in state:
    print('Yes')
else:
    print('No')

class LcaDoubling:
    """
    links[v] = { u1, u2, ... }  (u:隣接頂点, 親は含まない)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAを取得できるようにする
    """

    def __init__(self, n, links, root=0):
        self.depths = [-1] * n
        prev_ancestors = self._init_dfs(n, links, root)
        self.ancestors = [prev_ancestors]
        max_depth = max(self.depths)
        d = 1
        while d < max_depth:
            next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
            self.ancestors.append(next_ancestors)
            d <<= 1
            prev_ancestors = next_ancestors

    def _init_dfs(self, n, links, root):
        q = [(root, -1, 0)]
        direct_ancestors = [-1] * (n + 1)  # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
        while q:
            v, p, dep = q.pop()
            direct_ancestors[v] = p
            self.depths[v] = dep
            q.extend((u, v, dep + 1) for u in links[v])
        return direct_ancestors

    def get_lca(self, u, v):
        du, dv = self.depths[u], self.depths[v]
        if du > dv:
            u, v = v, u
            du, dv = dv, du
        tu = u
        tv = self.upstream(v, dv - du)
        if u == tv:
            return u
        for k in range(du.bit_length() - 1, -1, -1):
            mu = self.ancestors[k][tu]
            mv = self.ancestors[k][tv]
            if mu != mv:
                tu = mu
                tv = mv
        lca = self.ancestors[0][tu]
        assert lca == self.ancestors[0][tv]
        return lca

    def upstream(self, v, k):
        i = 0
        while k:
            if k & 1:
                v = self.ancestors[i][v]
            k >>= 1
            i += 1
        return v


def solve(n, m, k, ppp):
    parents = [-1]
    children = [[] for _ in range(n)]
    for i, p in enumerate(ppp, start=1):
        p -= 1
        parents.append(p)
        children[p].append(i)

    lca = LcaDoubling(n, links=children)
    order_limit = [-1] * n  # 左右の子、どちらを先に訪れなければならないか 0:左 1:右 -1:制約無し
    p_load = [0] * n  # ここで積んで親方面へ持ってくボールの数
    p_drop = [0] * n  # 親方面から持ってきてここで降ろすボールの数
    l_load = [0] * n  # 左（1つめ）の子へ持ってく
    l_drop = [0] * n
    r_load = [0] * n
    r_drop = [0] * n
    diff = [0] * n  # 親に繋がる辺を入って出るときに差し引き増えてるボールの数

    for _ in range(m):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        c = lca.get_lca(s, t)

        diff[s] += 1
        diff[t] -= 1

        if s == c:
            if len(children[s]) == 1:
                l_load[s] += 1
            else:
                # t が c=s のどっちの子か特定
                v = children[c][0]
                d = lca.get_lca(t, v)
                if d == v:
                    l_load[s] += 1
                else:
                    r_load[s] += 1
            p_drop[t] += 1
        elif t == c:
            if len(children[t]) == 1:
                l_drop[t] += 1
            else:
                # s が c=t のどっちの子か特定
                v = children[c][0]
                d = lca.get_lca(s, v)
                if d == v:
                    l_drop[t] += 1
                else:
                    r_drop[t] += 1
            p_load[s] += 1
        else:
            p_load[s] += 1
            p_drop[t] += 1
            # c は子を2個持つこと確定。s,t がそれぞれ c のどっちの子か特定
            v = children[c][0]
            d = lca.get_lca(s, v)
            if d == v:
                ol = 0
            else:
                ol = 1
            if order_limit[c] == -1:
                order_limit[c] = ol
            elif order_limit[c] != ol:
                return 0

    MOD = 998244353
    q = [0]
    status = [0] * n
    dp = [[0] * (k + 1) for _ in range(n)]
    while q:
        v = q[-1]
        if status[v] == 0:
            status[v] = 1
            q.extend(children[v])
            continue

        q.pop()
        dpv = dp[v]
        if len(children[v]) == 0:
            pl = p_load[v]
            pd = p_drop[v]
            x_max = min(k, k + pd - pl)
            for x in range(pd, x_max + 1):
                dpv[x] = 1
        elif len(children[v]) == 1:
            c = children[v][0]
            d = diff[c]
            dpc = dp[c]
            pl = p_load[v]
            pd = p_drop[v]
            ll = l_load[v]
            ld = l_drop[v]
            x_min = max(0, pd, pd - ll - d, pd - ll - d + ld)
            x_max = min(k, k + pd - ll, k + pd - ll - d, k + pd - ll - d + ld - pl)
            for x in range(x_min, x_max + 1):
                dpv[x] = dpc[x - pd + ll]
        else:
            c0, c1 = children[v]
            pl = p_load[v]
            pd = p_drop[v]
            ll = l_load[v]
            ld = l_drop[v]
            rl = r_load[v]
            rd = r_drop[v]
            if order_limit[v] == 0:
                two_children_update(dpv, dp[c0], dp[c1], diff[c0], diff[c1], pl, pd, ll, ld, rl, rd, MOD)
            elif order_limit[v] == 1:
                two_children_update(dpv, dp[c1], dp[c0], diff[c1], diff[c0], pl, pd, rl, rd, ll, ld, MOD)
            else:
                two_children_update(dpv, dp[c0], dp[c1], diff[c0], diff[c1], pl, pd, ll, ld, rl, rd, MOD)
                two_children_update(dpv, dp[c1], dp[c0], diff[c1], diff[c0], pl, pd, rl, rd, ll, ld, MOD)

        if v > 0:
            p = parents[v]
            diff[p] += diff[v]

    return dp[0][0]


def two_children_update(dpv, dp0, dp1, d0, d1, pl, pd, ll, ld, rl, rd, MOD):
    x_min = max(0, pd, pd - ll - d0, pd - ll - d0 + ld, pd - ll - d0 + ld - rl - d1,
                pd - ll - d0 + ld - rl - d1 + rd)
    x_max = min(k, k + pd - ll, k + pd - ll - d0, k + pd - ll - d0 + ld - rl,
                k + pd - ll - d0 + ld - rl - d1, k + pd - ll - d0 + ld - rl - d1 + rd - pl)
    for x in range(x_min, x_max + 1):
        dpv[x] += dp0[x - pd + ll] * dp1[x - pd + ll + d0 - ld + rl]
        dpv[x] %= MOD


n, m, k = map(int, input().split())
ppp = list(map(int, input().split()))

ans = solve(n, m, k, ppp)
print(ans)