結果
問題 | No.2360 Path to Integer |
ユーザー |
![]() |
提出日時 | 2023-07-10 01:08:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 204 ms / 2,500 ms |
コード長 | 1,946 bytes |
コンパイル時間 | 1,816 ms |
コンパイル使用メモリ | 198,112 KB |
最終ジャッジ日時 | 2025-02-15 09:23:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const ll modc = 998244353;ll N, ans=0;vector<ll> xx1(1e5), yy1(1e5), xx2(1e5), yy2(1e5), a(1e5), ten(1e5);vector<vector<ll>> E(1e5);void dfs1(ll from, ll p){xx1[from] = 1; yy1[from] = 1;for (auto to : E[from]){if (to == p) continue;dfs1(to, from);xx1[from] += xx1[to];xx1[from] %= modc;yy1[from] += yy1[to];yy1[from] %= modc;}yy1[from] *= ten[from];yy1[from] %= modc;}void dfs2(ll from, ll p){ll xx = 1, yy = 1;for (auto to : E[from]){if (to == p){xx += xx2[from];yy += yy2[from];xx %= modc;yy %= modc;continue;}xx += xx1[to];yy += yy1[to];xx %= modc;yy %= modc;}for (auto to : E[from]){if (to == p) continue;xx2[to] = (xx+modc-xx1[to]) % modc;yy2[to] = ((yy+modc-yy1[to]) % modc * ten[from]) % modc;dfs2(to, from);}}void dfs3(ll from, ll p){ll cnt = (yy2[from] * xx1[from]) % modc;for (auto to : E[from]){if (to == p) continue;cnt += (xx2[to] * yy1[to]) % modc;cnt %= modc;dfs3(to, from);}ans += (cnt * a[from]) % modc;ans %= modc;}ll ndig(ll X){return (X == 0 ? 0 : ndig(X/10)+1);}ll tn(ll n){ll res = 1;for (int i=0; i<n; i++){res *= 10;res %= modc;}return res;}int main(){ll x, y;cin >> N;for (int i=0; i<N; i++){cin >> a[i];ten[i] = tn(ndig(a[i]));a[i] %= modc;ans += (a[i] * N) % modc;ans %= modc;}for (int i=0; i<N-1; i++){cin >> x >> y; x--; y--;E[x].push_back(y);E[y].push_back(x);}dfs1(0, -1);dfs2(0, -1);dfs3(0, -1);cout << ans << endl;return 0;}