問題一覧 > 通常問題

No.1769 Don't Stop the Game

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 23
作問者 : first_vil / テスター : ygussany polylogK
お気に入りにしたユーザー ProblemId : 7192 / 自分の提出
問題文最終更新日: 2021-11-26 14:45:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 325 (順位表) の他の問題:

Note

The time limit for this problem is $3$ seconds.

Problem Statement

There is a tree with $N$ vertices. The $i\ (1 \le i \le N-1)$-th edge bidirectionally connects vertices $A_i$ and $B_i$, and its weight is $C_i$.

There are $N(N-1)$ integer pairs $(i,j)$ satisfying $1 \le i,j \le N$ and $i \neq j$. How many of them satisfy the following condition?

  • In the process of moving from vertex $i$ to vertex $j$ along the shortest path, the bitwise XOR (exclusive OR) of the weights of the edges traversed is always at least $1$.

Input

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$
  • All input values are integers.
  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \lt B_i \le N$
  • $0 \le C_i \lt 2^{30}$
  • The given graph is a tree.

Output

Output the answer, followed by a newline.

Sample

Sample 1
Input
4
2 3 2
2 4 1
1 4 3
Output
10

When moving from vertex $1$ to vertex $3$, the XOR of the edge weights becomes $3\ \mathrm{xor}\ 1\ \mathrm{xor}\ 2=0$, so the condition is not satisfied. The same applies when moving from vertex $3$ to vertex $1$.

Sample 2
Input
5
1 2 1
1 3 1
1 4 1
1 5 1
Output
8

Sample 3
Input
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
Output
305

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