結果
問題 | No.1843 Tree ANDistance |
ユーザー |
👑 |
提出日時 | 2022-02-18 21:46:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 676 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 232,576 KB |
最終ジャッジ日時 | 2024-06-29 08:39:16 |
合計ジャッジ時間 | 15,728 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 TLE * 1 |
ソースコード
import sys sys.setrecursionlimit(10 ** 9) MOD = 10 ** 9 + 7 n = int(input()) edges = [[] for _ in range(n)] for _ in range(n - 1): a, b, c = map(int, input().split()) a -= 1 b -= 1 edges[a].append((b, c)) edges[b].append((a, c)) dp = [[1] * 30 for _ in range(n)] ans = 0 bi = [1 << i for i in range(30)] def dfs(pos, bpos): global ans for npos, c in edges[pos]: if npos == bpos: continue dfs(npos, pos) for i in range(30): if c >> i & 1: ans += dp[pos][i] * dp[npos][i] * bi[i] ans %= MOD dp[pos][i] += dp[npos][i] dfs(0, -1) print(ans)