結果

問題 No.1843 Tree ANDistance
コンテスト
ユーザー koheijkt
提出日時 2026-01-14 11:47:47
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 769 ms / 2,000 ms
コード長 2,362 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 319 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 158,056 KB
最終ジャッジ日時 2026-01-14 11:48:07
合計ジャッジ時間 17,417 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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))

limit = 30
#limit = 3
DP = [[0] * (limit) for _ in range(N + 1)]

# 1根付き木で解く
par = [-1] * (N + 1)
weight = [-1] * (N + 1)
stack = [~1, 1]
while stack:
    pos = stack.pop()
    if pos > 0:
        # 行きがけ
        # 子どもをstackに詰める
        oya = par[pos]
        for nex, w in G[pos]:
            if nex == oya:
                continue
            par[nex] = pos
            weight[nex] = w
            stack.append(~nex)
            stack.append(nex)
    else:
        if par[~pos] == -1:
            continue
        # 帰りがけ
        # 親に計上
        w = weight[~pos]
        oya = par[~pos]
        for i in range(limit):
            if (w >> i) & 1 == 1:
                DP[oya][i] += DP[~pos][i] + 1
                DP[oya][i] %= MOD
#print(DP)

# 全方位木DP
stack = [~1, 1]
cnt = [0] * limit
while stack:
    pos = stack.pop()
    if pos > 0:
        # 行きがけ
        # DPの調整
        oya = par[pos]
        # 根の移動に伴う調整
        if pos != 1:
            w = weight[pos]
            weight[pos] = -1
            weight[oya] = w
            for i in range(limit):
                if (w >> i) & 1 == 1:
                    DP[oya][i] -= DP[pos][i] + 1
                    DP[pos][i] += DP[oya][i] + 1 # 更新後のDP[pos] を追加する
        # 答えを出す
        for i in range(limit):
            cnt[i] += DP[pos][i]
            cnt[i] %= MOD

        for nex, w in G[pos]:
            if nex == oya:
                continue
            stack.append(~nex)
            stack.append(nex)
    else:
        if par[~pos] == -1:
            continue
        # 帰りがけ
        oya = par[~pos] # 戻し先

        # weight 戻し
        w = weight[oya]
        weight[~pos] = w
        weight[oya] = -1

        # DP戻し
        for i in range(limit):
            if (w >> i) & 1 == 1:
                # ~pos から oya（戻し先）の寄与を削る
                DP[~pos][i] -= DP[oya][i] + 1
                DP[oya][i] += DP[~pos][i] + 1
#print(DP)
#print(cnt)
ans = 0
for i in range(limit):
    ans += (1<<i) * cnt[i]
    ans %= MOD
ans *= pow(2, -1, MOD)
ans %= MOD
print(ans)
0