結果
問題 | No.1843 Tree ANDistance |
ユーザー |
|
提出日時 | 2022-02-18 22:20:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 572 ms / 2,000 ms |
コード長 | 1,115 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 81,780 KB |
実行使用メモリ | 197,636 KB |
最終ジャッジ日時 | 2024-06-29 09:12:16 |
合計ジャッジ時間 | 11,818 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N = int(input()) edge = [[] for v in range(N)] for _ in range(N-1): a,b,c = mi() edge[a-1].append((b-1,c)) edge[b-1].append((a-1,c)) parent = [(-1,-1) for v in range(N)] topo = [] deq = deque([0]) while deq: v = deq.popleft() topo.append(v) for nv,c in edge[v]: if nv==parent[v][0]: continue parent[nv] = (v,c) deq.append(nv) dp = [[(0,1) for k in range(30)] for v in range(N)] for v in topo[::-1]: for nv,c in edge[v]: if nv==parent[v][0]: continue for k in range(30): x,y = dp[v][k] z,w = dp[nv][k] if c>>k & 1: dp[v][k] = (x+z+y*w,y+w) else: dp[v][k] = (x+z,y) res = 0 for k in range(30): res += dp[0][k][0] * pow(2,k,10**9+7) print(res % (10**9 + 7))