結果

問題 No.2949 Product on Tree
ユーザー InTheBloomInTheBloom
提出日時 2024-11-04 18:18:40
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 1,091 bytes
コンパイル時間 5,738 ms
コンパイル使用メモリ 174,468 KB
実行使用メモリ 37,504 KB
最終ジャッジ日時 2024-11-04 18:19:06
合計ジャッジ時間 24,528 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 295 ms
25,268 KB
testcase_04 AC 278 ms
25,280 KB
testcase_05 AC 285 ms
25,320 KB
testcase_06 AC 310 ms
25,344 KB
testcase_07 AC 279 ms
25,380 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 312 ms
26,164 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 284 ms
29,224 KB
testcase_14 WA -
testcase_15 AC 293 ms
32,828 KB
testcase_16 AC 283 ms
31,252 KB
testcase_17 WA -
testcase_18 AC 283 ms
31,504 KB
testcase_19 AC 314 ms
33,304 KB
testcase_20 AC 287 ms
32,864 KB
testcase_21 AC 291 ms
32,964 KB
testcase_22 AC 284 ms
34,256 KB
testcase_23 AC 291 ms
25,272 KB
testcase_24 AC 299 ms
25,292 KB
testcase_25 AC 291 ms
25,308 KB
testcase_26 AC 288 ms
25,320 KB
testcase_27 WA -
testcase_28 AC 319 ms
25,584 KB
testcase_29 AC 290 ms
25,704 KB
testcase_30 AC 288 ms
26,180 KB
testcase_31 AC 291 ms
27,308 KB
testcase_32 WA -
testcase_33 AC 295 ms
30,532 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 308 ms
35,704 KB
testcase_37 AC 298 ms
35,908 KB
testcase_38 AC 295 ms
33,316 KB
testcase_39 AC 351 ms
33,728 KB
testcase_40 WA -
testcase_41 AC 307 ms
35,028 KB
testcase_42 AC 301 ms
37,504 KB
testcase_43 WA -
testcase_44 AC 174 ms
23,356 KB
testcase_45 AC 220 ms
25,488 KB
testcase_46 AC 195 ms
25,380 KB
testcase_47 AC 136 ms
17,280 KB
testcase_48 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N = readln.chomp.to!int;
    auto A = readln.split.to!(int[]);

    const long MOD = 998244353;

    auto graph = new int[][](N, 0);
    foreach (i; 0..N - 1) {
        int U, V; readln.read(U, V);
        U--, V--;
        graph[U] ~= V;
        graph[V] ~= U;
    }

    long ans = 0;
    auto dp = new long[](N);
    // dp[i] := iを根とする部分木に属するすべての頂点jに対して、f(i, j)の総和

    void dfs (int pos, int par) {
        long s = 0;
        foreach (to; graph[pos]) {
            if (to == par) continue;
            dfs(to, pos);

            ans += s * A[pos] % MOD * dp[to] % MOD;
            s += dp[to];
            if (MOD <= s) s -= MOD;
        }
        dp[pos] = (s + 1) * A[pos] % MOD;
        ans += dp[pos] - A[pos];
        if (MOD <= ans) ans -= MOD;
    }

    dfs(0, -1);

    writeln(ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0