結果

問題 No.2360 Path to Integer
コンテスト
ユーザー LyricalMaestro
提出日時 2026-01-03 20:48:24
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 813 ms / 2,500 ms
コード長 3,054 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 366 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 168,084 KB
最終ジャッジ日時 2026-01-03 20:48:32
合計ジャッジ時間 7,679 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2360

from  collections import deque

MOD = 998244353


def main():
    N = int(input())
    A = list(map(int, input().split()))
    next_nodes = [[] for _ in range(N)]
    for _ in range(N - 1):
        u ,v = map(int, input().split())
        next_nodes[u - 1].append(v - 1)
        next_nodes[v - 1].append(u - 1)

    # 数字の長さを計算
    number_lengths = [len(str(a)) for a in A]

    pow10 = [0] * 11
    p = 1
    for i in range(11):
        pow10[i] = p
        p *= 10
        p %= MOD

    # 全方位木DPで解く
    stack = deque()
    parents = [-2] * N
    total_child_nums = [0] * N
    next_child_nums = [{} for _ in range(N)]
    total_child_weights = [0 for _ in range(N)]
    next_weights = [{} for _ in range(N)]
    stack.append((0, 0))
    parents[0] = -1
    while len(stack) > 0:
        v, index = stack.pop()
        while index < len(next_nodes[v]):
            w = next_nodes[v][index]
            if parents[v] == w:
                index += 1
                continue

            parents[w] = v
            stack.append((v, index +1))
            stack.append((w, 0))
            break

        if index == len(next_nodes[v]):
            p = parents[v]
            if p != -1:
                total_child_weights[p] += (pow10[number_lengths[v]] * total_child_weights[v]) % MOD
                total_child_weights[p] %= MOD
                total_child_weights[p] += pow10[number_lengths[v]]
                total_child_weights[p] %= MOD
                next_weights[p][v] = (pow10[number_lengths[v]] * total_child_weights[v]) % MOD
                next_weights[p][v] += pow10[number_lengths[v]]
                next_weights[p][v] %= MOD

                total_child_nums[p] += 1 + total_child_nums[v]
                next_child_nums[p][v] = 1 + total_child_nums[v]

    queue = deque()
    queue.append((0, -1, -1))
    while len(queue) > 0:
        v, weight0, c_num = queue.popleft()
        if parents[v] != -1:
            p = parents[v]
            total_child_weights[v] += weight0
            total_child_weights[v] %= MOD
            next_weights[v][p] = weight0

            total_child_nums[v] += c_num
            next_child_nums[v][p] = c_num

        for w in next_nodes[v]:
            if w == parents[v]:
                continue

            nw = next_weights[v][w]
            weight = (total_child_weights[v] - nw) % MOD
            weight *= pow10[number_lengths[v]]
            weight %= MOD
            weight += pow10[number_lengths[v]]
            weight %= MOD

            child_num = N - next_child_nums[v][w]
            queue.append((w, weight, child_num))

    answer = 0
    for v in range(N):
        a = A[v]
        for w in next_nodes[v]:
            x = a * next_weights[v][w]
            x %= MOD
            y = N - next_child_nums[v][w]
            ans = (y * x) % MOD
            answer += ans
            answer %= MOD

        answer += (N * a) % MOD
        answer %= MOD
    print(answer)






if __name__ == "__main__":
    main()
0