結果

問題 No.2638 Initial fare
ユーザー parukiparuki
提出日時 2024-03-03 01:54:16
言語 JavaScript
(node v21.7.1)
結果
RE  
実行時間 -
コード長 944 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 6,676 KB
実行使用メモリ 109,780 KB
最終ジャッジ日時 2024-03-03 01:54:39
合計ジャッジ時間 21,089 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
37,760 KB
testcase_01 AC 66 ms
37,760 KB
testcase_02 AC 66 ms
37,632 KB
testcase_03 AC 67 ms
37,760 KB
testcase_04 AC 1,014 ms
102,792 KB
testcase_05 AC 1,018 ms
106,012 KB
testcase_06 AC 67 ms
37,888 KB
testcase_07 AC 1,005 ms
107,104 KB
testcase_08 AC 873 ms
104,732 KB
testcase_09 AC 943 ms
109,780 KB
testcase_10 AC 934 ms
108,900 KB
testcase_11 AC 69 ms
37,888 KB
testcase_12 AC 980 ms
105,632 KB
testcase_13 AC 910 ms
100,900 KB
testcase_14 AC 935 ms
107,040 KB
testcase_15 AC 985 ms
108,004 KB
testcase_16 AC 67 ms
38,016 KB
testcase_17 AC 973 ms
106,384 KB
testcase_18 AC 950 ms
105,616 KB
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 AC 67 ms
37,888 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 67 ms
37,888 KB
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

Main(require("fs").readFileSync("/dev/stdin", "utf8").split(/\r\n|\n|\r/));

function dfs(G, u, p) {
    // 1, 2, 3
    let sum = [0, 0, 0];
    let res = [1, 0, 0, 0];

    G[u].forEach(v => {
        if(v==p)return;
        sub = dfs(G, v, u);
        for(let i=0; ; ++i) {
            res[3] += sub[i];
            if(i==3)break;
            for(let j=0; i+j+2<=3; ++j) {
                res[3] += sub[i] * sum[j];
            }
        }
        for(let i=0; i<3; ++i) {
            sum[i] += sub[i];
        }
    });
    for(let i=0; i<2; ++i){
        res[i+1] += sum[i];
    }
    return res;
}

function Main(lines) {
    const N = parseInt(lines[0]);
    let G = Array(N);
    for(let i=0; i<N; ++i) G[i] = Array(0);
    for(let i=0; i<N-1; ++i) {
        const uv = lines[i+1].split(" ").map(Number);
        G[uv[0]-1].push(uv[1]-1);
        G[uv[1]-1].push(uv[0]-1);
    }

    const ans = dfs(G, 0, -1)[3];
    console.log(ans);
}
0