arc 045 C - エックスオア多橋君 (python)

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるときも答えに含めるため、最初に D [ 0 ] = 1 としておく。

import sys
sys.setrecursionlimit(10**7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

n, x = map(int, readline().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v, c = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append((v,c))
    g[v].append((u,c))

D = defaultdict(int)
D[0] += 1
ans = 0
def dfs(now, prev, xors):
  global ans
  for next,co in g[now]:
    if next != prev:
      xx = xors^co
      ans += D[xx^x]
      D[xx] += 1
      dfs(next, now, xx)
  return ans

print(dfs(0, -1, 0))