AT_arc045_c [ARC045C] エックスオア多橋君

[problemUrl]: https://atcoder.jp/contests/arc045/tasks/arc045_c 多橋君は橋が大好きです。したがって、全ての辺が橋(グラフ理論用語)となる木と呼ばれるグラフが大好きです。また、多橋君は最近学校でXORについて学びました。そこで、次のような問題について考えています。 $ N $ 頂点と $ N-1 $ 本の辺からなる連結な無向グラフ、つまり木が与えられます。各頂点は、それぞれ頂点 $ 1 $、頂点 $ 2 $、…、頂点 $ N $ と呼ばれます。各辺にはそれぞれ非負整数のコストが割り振られています。 整数 $ X $ が与えられるので、頂点 $ a $ と頂点 $ b $ を結ぶ単純パス(同じ辺を二度通らないパス、木においては必ず $ 1 $ つだけ存在する)上の辺のコストの$ \rm{xor} $和が $ X $ になるような組 $ (a,b) $ ($ 1≦a＜b≦N $)の総数を求めてください。 ただし$ \rm{xor} $和とは、いくつかの整数 $ A_1,A_2,… $ があったとき、それらの2進表現のビット毎の排他的論理和 $ A_1 $ $ \rm{xor} $ $ A_2 $ $ \rm{xor}… $ により得られる値のことを表します。 例えば、$ 1 $ $ \rm{xor} $ $ 2 $ $ \rm{xor} $ $ 5 $ は $ 6 $ です。 あなたの仕事は、多橋君の代わりにこの問題を解くことです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ : $ x_{N-1} $ $ y_{N-1} $ $ c_{N-1} $ - $ 1 $ 行目には、グラフの頂点数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 100,000) $ と問題文中の整数 $ X\ (0≦X≦10^9) $ が与えられる。 - 続く $ N-1 $ 行には、グラフの $ N-1 $ 本の辺の情報が与えられる。このうち $ i(1≦i≦N-1) $ 行目には、$ i $ 番目の辺が結ぶ $ 2 $ つの頂点 $ x_i,y_i(1≦x_i,y_i≦N) $ とコスト $ c_i\ (0≦c_i≦10^9) $ が与えられる。 - 与えられるグラフは連結であることが保証される。

$ 1 $ 行目に問題文中で求められている答えを出力せよ。末尾に改行を入れること。

### Sample Explanation 1 $ (a,b)=(1,5),(4,5),(5,6) $ のとき、パス上の辺のコストの$ \rm{xor} $和が $ 7 $($ 2 $進表記で$ 111 $) となるので答えは $ 3 $ となる。 この入力例に対するグラフは下図のようになる。コストについては、その$ 10 $進表記と$ 2 $進表記を表示している。 !\[サンプル1説明\](https://arc045.contest.atcoder.jp/img/arc/045/xpEYc7xpC8hMWHraQ2pCmb9GbuAdaQR4/c1.png)