問題一覧 > 通常問題

No.2360 Path to Integer

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : 遭難者遭難者 / テスター : 👑 ygussanyygussany とりゐとりゐ
2 ProblemId : 8804 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-09 20:17:29

問題文

$N$ 頂点の木 $G$ が与えられます。この木 $G$ の $i$ 番目 $(1\le i\le N-1)$ の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、 $i$ 番目 $(1\le i\le N)$ の頂点には文字列 $A_i$ が書かれています。

$f(i,j)$ を以下の手順で得られる整数と定義します。

  • $S$ を空文字列とする。
  • 頂点 $i$ から頂点 $j$ への最短パス上にある頂点全て対し、頂点 $i$ から順番にその頂点に書かれた文字列を $S$ の末尾に連結する。
  • $S$ を整数として見た値が $f(i,j)$ である。

$\displaystyle \sum_{i=1}^N\sum_{j=1}^Nf(i,j)$ を $998244353$ で割った余りを求めてください。

制約

  • $2\le N\le 10^5$
  • $A_i$ は 0 から 9 までの数字からなる長さ $1$ 以上 $10$ 以下の文字列で、先頭が 0 でない。
  • $1\le u_i,v_i\le N$
  • 与えられるグラフは木である。

    • 入力

    $N$
$A_1$ $A_2$ $\ldots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

    出力

    $\displaystyle \sum_{i=1}^N\sum_{j=1}^Nf(i,j)$ を $998244353$ で割った余りを出力してください。

    サンプル

    サンプル1
    入力
    3
2 1 12
1 2
2 3
    出力
    3605

    例えば $f(1,3)=2112$ です。これは、頂点 $1,2,3$ にそれぞれ $2,1,12$ が書かれており、これらを連結すると $2112$ になるからです。
    求める答えは $2+21+2112+12+1+112+1212+121+12=3605$ なので、 $3605$ を出力してください。

    サンプル2
    入力
    4
998244353 998244353 998244353 1
1 2
1 3
1 4
    出力
    435653094

    $998244353$ で割った余りを出力してください。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。