問題一覧 > 通常問題

No.2360 Path to Integer

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

問題文

NN 頂点の木 GG が与えられます。この木 GGii 番目 (1iN1)(1\le i\le N-1) の辺は頂点 uiu_i と頂点 viv_i を結んでいます。また、 ii 番目 (1iN)(1\le i\le N) の頂点には文字列 AiA_i が書かれています。

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

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

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

制約

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

    NN
    A1A_1 A2A_2 \ldots ANA_N
    u1u_1 v1v_1
    u2u_2 v2v_2
    \vdots
    uN1u_{N-1} vN1v_{N-1}
    

    出力

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

    サンプル

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

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

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

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

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