問題一覧 > 通常問題

No.1769 Don't Stop the Game

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : first_vilfirst_vil / テスター : polylogKpolylogK 👑 ygussanyygussany
2 ProblemId : 7192 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-26 14:45:32

注意

この問題の実行時間制限は $3$ 秒です。

問題文

$N$ 頂点からなる木があります。$i\ (1 \le i \le N-1)$ 本目の辺は頂点 $A_i$ と頂点 $B_i$ を双方向に結び、重みは $C_i$ です。

$1 \le i,j \le N$ かつ $i \neq j$ を満たす整数組 $(i,j)$ は $N(N-1)$ 通りありますが、それらのうち以下の条件を満たすものはいくつありますか?

  • 頂点 $i$ から頂点 $j$ まで最短経路に沿って移動する過程において、通過した辺の重みのビットごとの XOR(排他的論理和)は常に $1$ 以上である。

入力

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$
  • 入力はすべて整数
  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \lt B_i \le N$
  • $0 \le C_i \lt 2^{30}$
  • 与えられるグラフは木

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
2 3 2
2 4 1
1 4 3
出力
10

頂点 $1$ から頂点 $3$ まで移動すると辺の重みの XOR は $3\ \mathrm{xor}\ 1\ \mathrm{xor}\ 2=0$ となるので条件を満たしません。頂点 $3$ から頂点 $1$ まで移動する場合も同様です。

サンプル2
入力
5
1 2 1
1 3 1
1 4 1
1 5 1
出力
8

サンプル3
入力
20
18 20 15
17 18 6
1 14 13
6 18 13
11 16 11
2 19 13
7 15 5
10 14 12
5 8 12
7 9 15
3 10 2
12 14 4
2 15 3
3 17 6
3 4 0
10 11 2
2 3 7
2 13 3
3 8 11
出力
305

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。