りんご拾い（情報を持ちながらの移動）

今回は paiza の 「りんご拾い（情報を持ちながらの移動）」の問題に挑戦！

📘 問題概要

• 頂点数 N のグラフが与えられる
• 辺は N-1 本で、グラフは 一直線（一本道）
  • 分岐なし
  • ループなし
• 各頂点には「りんごの数」が置かれている
• 頂点 1 からスタート
• 後戻りせず、行き止まりまで進む
• 進んだ順にりんごを拾う

🧩 入力

• N
  → 頂点の数
• a_i b_i（N-1行）
  → 頂点 a_i と b_i が辺でつながっている
• A_j（N行）
  → 頂点 j に置かれているりんごの数

🎯 出力

• 頂点1から
  k 頂点分進んだ時点で持っているりんごの累積数 S_k
• k = 0 ～ N-1 まで、N行出力

入力例:

3
1 3
2 3
5
1
7

出力例:

5
12
13

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

// 入力を1行ずつ配列に保存
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    // 頂点数
    const N = Number(lines[0]);

    // 辺の情報（N-1 本）
    const points = lines.slice(1, N).map(p => p.split(' ').map(Number));

    // 各頂点のりんごの数
    const apple = lines.slice(N).map(Number);
    
    // 隣接リストでグラフを作成
    const grapth = Array.from({ length: N }, () => []);
    for (const p of points) {
        const [a, b] = p;
        grapth[a-1].push(b-1);
        grapth[b-1].push(a-1);
    }
    
    // 実際に進んだ順番を保存
    const visit = [];
    // 訪問済み管理（後戻り防止）
    const done = Array(N).fill(false);
    
    // 頂点1（0-indexedで0）からスタート
    visit.push(0);
    done[0] = true;
    
    // 一本道なので、未訪問の隣接頂点へ進み続ける
    while (visit.length !== N) {
        const now = visit[visit.length - 1];
        
        for (const next of grapth[now]) {
            if (!done[next]) {
                visit.push(next);
                done[next] = true;
                break;
            }
        }
    }
    
    // 進んだ順にりんごを加算して出力
    let ans = 0;
    for (const v of visit) {
        ans += apple[v];
        console.log(ans);
    }
});

🔍コードの流れ

• 標準入力からすべての行を lines 配列に読み込む
• 1行目から頂点数 N を取得する
• 次の N-1 行から辺の情報を取得する
• 残りの N 行から各頂点のりんごの数を取得する
• 隣接リストを使ってグラフを作成する
• 頂点1からスタートするため、visit に 0 を入れ訪問済みにする
• グラフが一本道なので、未訪問の隣接頂点へ順に進んでいき、進んだ順を visit に保存する
• visit に保存された順番でりんごを足していく
• 各時点での累積りんご数を出力する

📝 まとめ

• 一本道のグラフでは、「未訪問の隣接頂点に進むだけ」で経路が一意に決まる
• 訪問管理（done 配列）があれば後戻りを防げる
• この問題でも
  • 実際に必要なのは「進んだ順番」
  • 記録できれば、後の処理（累積和）は簡単
• 「グラフ」＋「累積和」は、探索 → 順序保存 → 計算 の流れで考えると整理しやすい

🛠 解くためにやったこと

• 辺情報から 隣接リスト を作る
• 頂点1からスタートする
• すでに通った頂点には戻らないようにする
• 一本道なので、今いる頂点の 未訪問の隣接頂点は1つ
• 進んだ順番を配列に記録する
• その順番でりんごを足していき、累積和を出力する