結果

問題 No.1103 Directed Length Sum
ユーザー marroncastlemarroncastle
提出日時 2020-09-13 05:16:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,547 ms / 3,000 ms
コード長 745 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 87,084 KB
実行使用メモリ 262,040 KB
最終ジャッジ日時 2023-08-30 23:44:11
合計ジャッジ時間 16,159 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
71,268 KB
testcase_01 AC 68 ms
71,588 KB
testcase_02 AC 730 ms
262,040 KB
testcase_03 AC 775 ms
259,656 KB
testcase_04 AC 948 ms
134,972 KB
testcase_05 AC 1,547 ms
173,696 KB
testcase_06 AC 585 ms
114,624 KB
testcase_07 AC 177 ms
86,456 KB
testcase_08 AC 234 ms
90,952 KB
testcase_09 AC 137 ms
83,092 KB
testcase_10 AC 304 ms
96,348 KB
testcase_11 AC 938 ms
139,924 KB
testcase_12 AC 570 ms
115,116 KB
testcase_13 AC 315 ms
96,904 KB
testcase_14 AC 131 ms
81,560 KB
testcase_15 AC 450 ms
106,860 KB
testcase_16 AC 1,059 ms
147,120 KB
testcase_17 AC 1,110 ms
150,032 KB
testcase_18 AC 298 ms
96,276 KB
testcase_19 AC 973 ms
141,404 KB
testcase_20 AC 164 ms
84,412 KB
testcase_21 AC 226 ms
89,572 KB
testcase_22 AC 896 ms
129,824 KB
testcase_23 AC 497 ms
108,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.readline

def dfs(start):
  global ans,mod
  stack = [start]
  depth = [-1]*N
  child_num = [0]*N
  depth[start] = 0
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if depth[u]==-1: #前半
        marker = 1
        depth[u]=depth[v]+1
        stack.append(u)
      else: #後半
        ans += (depth[v]+1)*(child_num[u]+1)
        child_num[v] += child_num[u]+1
        ans %= mod
    if marker==0: #後半だったら
      stack.pop()
  return

N = int(input())
mod = 10**9+7
edge = [[] for _ in range(N)]
roots = [True]*N
for i in range(N-1):
  a,b = list(map(int, input().split()))
  roots[b-1] = False
  edge[a-1].append(b-1)

root = roots.index(True)
ans = 0
dfs(root)
print(ans)
0