結果

問題 No.1843 Tree ANDistance
コンテスト
ユーザー koheijkt
提出日時 2026-01-13 23:28:09
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 1,600 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 280 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 391,396 KB
最終ジャッジ日時 2026-01-13 23:28:34
合計ジャッジ時間 22,284 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(10**8)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
MOD = 10**9+7
N = int(input())
G = [list() for _ in range(N + 1)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    G[u].append((v, w))
    G[v].append((u, w))

# DP[i]
# 部分木iにおいて、この問題を解く
limit = 30
DP = [[0] * (limit) for _ in range(N + 1)]
def dfs(pos, pre):
    for nex, w in G[pos]:
        if nex == pre:
            continue
        dfs(nex, pos)
        # 親に計上
        for i in range(limit):
            if (w >> i) & 1 == 1:
                # 2**i の部門において計上
                DP[pos][i] += DP[nex][i] + 1
    return

dfs(1, 0)

# 全方位木DPを解く
cnt = [0] * limit
def dfs2(pos, pre):
    # pos が根になったときの、DP が答え
    # DP の内容を集計する
    for i in range(limit):    
        cnt[i] += DP[pos][i]
        cnt[i] %= MOD

    # 根の移動
    for nex, w in G[pos]:
        if nex == pre:
            continue
        # 設定のバックアップ
        memo1 = DP[pos][:]
        memo2 = DP[nex][:]
        # 根の移動に伴う調整
        for i in range(limit):
            if (w >> i) & 1 == 1:
                DP[pos][i] -= DP[nex][i] + 1
                DP[nex][i] += DP[pos][i] + 1 # 更新後のDP[pos] を追加する
        dfs2(nex, pos)
        # リストアする
        DP[pos] = memo1[:]
        DP[nex] = memo2[:]
    return

dfs2(1, 0)
ans = 0
for i in range(limit):
    ans += (1<<i) * cnt[i]
    ans %= MOD
ans *= pow(2, -1, MOD)
ans %= MOD
print(ans)
0