概要

この問題は、根付き木において各頂点から根（広場 1）までのパス上にある頂点の重み（混雑係数）の合計を求め、それに各頂点の人数を掛け合わせた総和を求める問題です。

考察

問題の数式を整理する

求める「混雑度」は以下の式で表されます。 $\( \text{混雑度} = \sum_{i=2}^{N} (B_i \times \text{広場 } i \text{ から広場 } 1 \text{ までのパス上の } A_j \text{ の総和}) \)$

ここで、\(S_i\) を「広場 \(i\) から広場 \(1\) までのパス上にある全広場の混雑係数 \(A_j\) の総和」と定義すると、求める値は \(\sum_{i=2}^{N} B_i S_i\) と非常にシンプルな形になります。

素朴な方法とその限界

各広場 \(i\) について、親を辿って広場 \(1\) に着くまで \(A_j\) を足していく方法が考えられます。しかし、木が細長い「直線状」の構造をしている場合、1つのパスの計算に \(O(N)\) かかり、全体で \(O(N^2)\) の計算量となります。\(N = 3 \times 10^5\) という制約下では、これでは制限時間に間に合いません。

効率的な計算方法

木構造の性質を利用すると、\(S_i\) は親の情報を利用して効率的に計算できます。 広場 \(i\) の親を \(P_i\) とすると、以下の関係が成り立ちます。 $\( S_i = S_{P_i} + A_i \)\( つまり、「広場 \)i$ から根までの合計」は、「親から根までの合計」に「自分自身の値」を足したものになります。

本問題では制約として \(1 \leq P_i < i\) が与えられています。これは、番号が小さい順に計算していけば、広場 \(i\) を計算する時には必ず親 \(P_i\) の計算が完了していることを意味します。そのため、複雑な探索（DFSなど）を実装しなくても、ループを回すだけで全ての \(S_i\) を \(O(N)\) で求めることができます。

アルゴリズム

1. 各広場 \(i\) のパス和を格納する配列 \(S\) を用意します。
2. 根である広場 \(1\) のパス和を \(S_1 = A_1\) とします。
3. \(i = 2, 3, \dots, N\) の順に、以下の計算を行います。
   • \(S_i = S_{P_i} + A_i\)
4. 全ての \(i = 2, 3, \dots, N\) について \(B_i \times S_i\) を計算し、その総和を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込み、パス和の計算（ループ1回）、最終的な総和の計算（ループ1回）のすべてが \(N\) に対して線形です。
• 空間計算量: \(O(N)\)
  • \(A, P, B, S\) を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 入力の高速化: Pythonで \(N = 3 \times 10^5\) 規模の入力を扱う場合、input() を繰り返すと遅いため、sys.stdin.read().split() などで一括で読み込むのが定石です。

• インデックスのずれ: 問題文は 1-indexed（広場 1〜N）ですが、プログラム内では 0-indexed（リストの 0〜N-1）として扱うことが多いため、親の番号 \(P_i\) から 1 を引くなどの調整が必要です。

• 大きな数値: 答えは最大で \(2^{63}-1\)（64bit整数の最大値程度）になる可能性がありますが、Pythonは標準で多倍長整数を扱えるため、オーバーフローの心配はありません。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    # N=3*10^5 という制約に対して高速に動作させるための手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 広場の数 N を取得
    N = int(input_data[0])
    
    # A: 各広場の混雑係数 A_1, A_2, ..., A_N
    # リストのインデックス 0 が広場 1 に対応するようにします
    A = list(map(int, input_data[1:N+1]))
    
    # P: 広場 i (2 <= i <= N) の親広場 P_i
    # P[0] は広場 2 の親、P[1] は広場 3 の親... という順で格納されます
    P = list(map(int, input_data[N+1:2*N]))
    
    # B: 各広場にいる人数 B_1, B_2, ..., B_N
    B = list(map(int, input_data[2*N:3*N]))
    
    # S[i]: 広場 i+1 から広場 1 までのパス上の混雑係数の総和
    # 動的計画法（または木上の計算）を用いて各広場からの累積和を求めます
    S = [0] * N
    S[0] = A[0]  # 広場 1 のパス和は A_1 自体
    
    # 制約 1 <= P_i < i により、親のパス和が常に先に計算されていることが保証されます
    # これにより、トポロジカル順序（この場合は単なるインデックス順）で計算可能です
    for i in range(1, N):
        # i は 0-indexed なので、広場番号としては i+1
        # その親の広場番号は P[i-1]
        parent_idx = P[i-1] - 1
        # 広場 i+1 のパス和 = 広場 i+1 の混雑係数 + 親広場のパス和
        S[i] = S[parent_idx] + A[i]
        
    # 全体の混雑度を計算します
    # 広場 1 にいる B_1 人は移動しないため、i=2 から N までの和をとります
    # (0-indexed では i=1 から N-1 まで)
    ans = 0
    for i in range(1, N):
        ans += B[i] * S[i]
        
    # 結果を出力
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。