結果

問題 No.1333 Squared Sum
ユーザー LyricalMaestro
提出日時 2024-11-06 02:20:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,767 ms / 2,000 ms
コード長 4,002 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 206,292 KB
最終ジャッジ日時 2024-11-06 02:21:19
合計ジャッジ時間 45,161 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

## https://yukicoder.me/problems/no/1333
from collections import deque
MOD= 10 ** 9 + 7
def main():
N = int(input())
next_nodes = [[] for _ in range(N)]
for _ in range(N - 1):
u, v, w = map(int, input().split())
next_nodes[u - 1].append((v - 1, w))
next_nodes[v - 1].append((u - 1, w))
# dp
parents = [-2] * N
parents_index = [-2] * N
parents_index2 = [-2] * N
total_child_num = [0 for _ in range(N)]
next_child_num = [[0] * len(next_nodes[v]) for v in range(N)]
total_dist_sum = [0 for _ in range(N)]
next_dist_sum = [[0] * len(next_nodes[v]) for v in range(N)]
total_dist2_sum = [0 for _ in range(N)]
next_dist2_sum = [[0] * len(next_nodes[v]) for v in range(N)]
parents[0] = -1
parents_index[0] = -1
parents_index2[0] = -1
stack = deque()
stack.append((0, 0))
while len(stack) > 0:
v, index = stack.pop()
while index < len(next_nodes[v]):
w = next_nodes[v][index][0]
if w == parents[v]:
parents_index[v] = index
index += 1
continue
parents[w] = v
parents_index2[w] = index
stack.append((v, index + 1))
stack.append((w, 0))
break
if index == len(next_nodes[v]):
p = parents[v]
if p != -1:
p_index2 = parents_index2[v]
total_child_num[p] += 1 + total_child_num[v]
next_child_num[p][p_index2] = 1 + total_child_num[v]
w = next_nodes[p][p_index2][1]
d1 = ((1 + total_child_num[v]) * w) % MOD
total_dist_sum[p] += (d1 + total_dist_sum[v]) % MOD
total_dist_sum[p] %= MOD
next_dist_sum[p][p_index2] = (d1 + total_dist_sum[v]) % MOD
d2 = ((1 + total_child_num[v]) * w) % MOD
d2 *= w
d2 %= MOD
d2_2 = (w * total_dist_sum[v]) % MOD
d2_2 *= 2
d2_2 %= MOD
d = (total_dist2_sum[v] +d2_2) % MOD
d += d2
d %= MOD
total_dist2_sum[p] += d
total_dist2_sum[p] %= MOD
next_dist2_sum[p][p_index2] = d
# queue Part
queue = deque()
queue.append((0, 0, 0, 0))
while len(queue) > 0:
v, c_c_num, c_d_sum, c_d2_sum = queue.popleft()
if parents[v] != -1:
p = parents[v]
p_index = parents_index[v]
total_child_num[v] += c_c_num
next_child_num[v][p_index] = c_c_num
total_dist_sum[v] += c_d_sum
total_dist_sum[v] %= MOD
next_dist_sum[v][p_index] = c_d_sum
total_dist2_sum[v] += c_d2_sum
total_dist2_sum[v] %= MOD
next_dist2_sum[v][p_index] = c_d2_sum
for i in range(len(next_nodes[v])):
v0 = next_nodes[v][i][0]
if v0 == parents[v]:
continue
c_num = total_child_num[v] - next_child_num[v][i]
d_sum = (total_dist_sum[v] - next_dist_sum[v][i]) % MOD
d2_sum = (total_dist2_sum[v] - next_dist2_sum[v][i]) % MOD
w = next_nodes[v][i][1]
next_c_num = c_num + 1
next_d_sum = ((1 + c_num) * w) % MOD
next_d_sum += d_sum
next_d_sum %= MOD
d2 = ((1 + c_num) * w) % MOD
d2 *= w
d2 %= MOD
d2_2 = (w * d_sum) % MOD
d2_2 *= 2
d2_2 %= MOD
d = (d2_sum + d2_2) % MOD
d += d2
d %= MOD
next_d2_sum = d
queue.append((v0, next_c_num, next_d_sum, next_d2_sum))
answer = 0
for i in range(N):
answer += total_dist2_sum[i]
answer %= MOD
answer *= pow(2, MOD - 2, MOD)
answer %= MOD
print(answer)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0