結果
問題 | No.2360 Path to Integer |
ユーザー |
👑 |
提出日時 | 2023-06-04 20:11:16 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,500 ms |
コード長 | 1,799 bytes |
コンパイル時間 | 153 ms |
コンパイル使用メモリ | 32,708 KB |
実行使用メモリ | 12,436 KB |
最終ジャッジ日時 | 2024-07-01 00:24:10 |
合計ジャッジ時間 | 1,428 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <stdio.h>const int Mod = 998244353;typedef struct Edge {struct Edge *next;int v, id, num;long long sum;} edge;int main(){int i, N, u, w;long long A[100001], AA[100001];edge *adj[100001] = {}, e[200001], *p;scanf("%d", &N);for (u = 1; u <= N; u++) {scanf("%lld", &(A[u]));for (AA[u] = 1; AA[u] <= A[u]; AA[u] *= 10);A[u] %= Mod;AA[u] %= Mod;}for (i = 0; i < N - 1; i++) {scanf("%d %d", &u, &w);e[i*2].v = w;e[i*2+1].v = u;e[i*2].id = i * 2;e[i*2+1].id = i * 2 + 1;e[i*2].num = 0;e[i*2+1].num = 0;e[i*2].sum = 0;e[i*2+1].sum = 0;e[i*2].next = adj[u];e[i*2+1].next = adj[w];adj[u] = &(e[i*2]);adj[w] = &(e[i*2+1]);}int par[100001] = {}, q[100001], head, tail, num[100001];long long sum[100001];par[1] = 1;q[0] = 1;for (head = 0, tail = 1; head < tail; head++) {u = q[head];for (p = adj[u]; p != NULL; p = p->next) {w = p->v;if (par[w] == 0) {par[w] = u;q[tail++] = w;}}}for (head--; head >= 0; head--) {u = q[head];for (p = adj[u], num[u] = 1, sum[u] = 1; p != NULL; p = p->next) {w = p->v;if (w == par[u]) continue;p->num = num[w];num[u] += p->num;p->sum = sum[w] * AA[w] % Mod;sum[u] += p->sum;}sum[u] %= Mod;}for (head = 1; head < tail; head++) {u = q[head];for (p = adj[u]; p != NULL; p = p->next) {w = p->v;if (w == par[u]) break;}p->num = N - num[u];p->sum = (sum[w] - e[p->id ^ 1].sum + Mod) * AA[w] % Mod;sum[u] += p->sum;if (sum[u] >= Mod) sum[u] -= Mod;}long long ans = 0;for (u = 1; u <= N; u++) {for (p = adj[u]; p != NULL; p = p->next) ans += A[u] * p->sum % Mod * (N - p->num) % Mod;ans += A[u] * N % Mod;}printf("%lld\n", ans % Mod);fflush(stdout);return 0;}