結果

問題 No.2638 Initial fare
コンテスト
ユーザー paruki
提出日時 2024-03-03 01:54:16
言語 JavaScript
(node v23.5.0)
結果
RE  
実行時間 -
コード長 944 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 110,780 KB
最終ジャッジ日時 2024-09-29 16:38:05
合計ジャッジ時間 18,803 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 RE * 7
権限があれば一括ダウンロードができます

ソースコード

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