結果

問題 No.3343 Distance Sum of Large Tree
コンテスト
ユーザー tassei903
提出日時 2025-10-25 15:07:42
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,082 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 104,240 KB
最終ジャッジ日時 2025-11-13 20:51:25
合計ジャッジ時間 4,759 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 10 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def naive(n, a, b, c, p):
    M = sum(a)
    g = [[] for i in range(M)]
    s = [0] * (n + 1)
    for i in range(n):
        s[i+1] = s[i] + a[i]
    
    for i in range(n):
        for j in range(a[i]-1):
            g[s[i] + j].append(s[i] + j + 1)
            g[s[i] + j + 1].append(s[i] + j)
        if i:
            u = s[p[i]] + c[i]
            v = s[i] + b[i]
            g[u].append(v)
            g[v].append(u)
    
    sub = [1] * M
    par = [-1] * M
    q = [0]
    seen = [0] * M
    seen[0] = 1
    et = []
    while q:
        x = q.pop()
        et.append(x)
        for y in g[x]:
            if seen[y]:
                continue
            seen[y] = 1
            q.append(y)
            par[y] = x
    
    ans = 0
    for x in et[1:][::-1]:
        ans += (M - sub[x]) * sub[x]
        sub[par[x]] += sub[x]

    return ans


n = int(input())
a = list(map(int, input().split()))
b = [-1] + [int(x) - 1 for x in input().split()]
c = [-1] + [int(x) - 1 for x in input().split()]
p = [-1] + [int(x) - 1 for x in input().split()]


print(naive(n, a, b, c, p))
0