結果

問題 No.1843 Tree ANDistance
ユーザー yudedakoyudedako
提出日時 2022-02-28 18:11:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 977 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 86,904 KB
実行使用メモリ 170,988 KB
最終ジャッジ日時 2023-09-21 02:42:55
合計ジャッジ時間 49,388 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 1,187 ms
170,988 KB
testcase_06 AC 1,348 ms
166,028 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 AC 1,074 ms
162,276 KB
testcase_13 AC 1,284 ms
150,952 KB
testcase_14 AC 271 ms
84,752 KB
testcase_15 AC 293 ms
85,988 KB
testcase_16 AC 249 ms
84,560 KB
testcase_17 AC 247 ms
84,060 KB
testcase_18 AC 212 ms
82,976 KB
testcase_19 AC 259 ms
85,296 KB
testcase_20 AC 243 ms
84,332 KB
testcase_21 AC 180 ms
80,672 KB
testcase_22 AC 179 ms
80,876 KB
testcase_23 AC 180 ms
80,720 KB
testcase_24 AC 177 ms
80,756 KB
testcase_25 AC 177 ms
80,772 KB
testcase_26 AC 176 ms
80,904 KB
testcase_27 AC 177 ms
80,916 KB
testcase_28 AC 1,806 ms
146,632 KB
testcase_29 AC 1,407 ms
121,184 KB
testcase_30 AC 1,515 ms
122,424 KB
testcase_31 TLE -
testcase_32 AC 1,824 ms
148,068 KB
testcase_33 AC 354 ms
106,168 KB
testcase_34 AC 811 ms
134,460 KB
testcase_35 AC 175 ms
80,680 KB
testcase_36 AC 174 ms
80,716 KB
testcase_37 AC 176 ms
80,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import queue

MOD = 1000000007
n = int(input())
edges = [map(int, input().split()) for _ in range(n - 1)]
graph = [[] for _ in range(n)]
for [a, b, c] in edges:
    graph[a - 1].append([b - 1, c])
    graph[b - 1].append([a - 1, c])
depth = [-1] * n
depth[0] = 0
queue = queue.Queue()
queue.put(0)
while not queue.empty():
    top = queue.get()
    for [to, _] in graph[top]:
        if depth[to] == -1:
            depth[to] = depth[top] + 1
            queue.put(to)
fromLeaf = sorted([i for i in range(n)], key = lambda i: depth[i], reverse = True)
result = 0
for d in range(30):
    onePath = 0
    endPath = [0] * n
    for node in fromLeaf:
        count = 0
        for [child, c] in graph[node]:
            if depth[child] <= depth[node] or ((c >> d) & 1) == 0:
                continue
            onePath += (count + 1) * (endPath[child] + 1)
            count += endPath[child] + 1
        endPath[node] = count
    result += onePath % MOD << d

print(result % MOD)
0