No.1769 Don't Stop the Game
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もしくは右上の雲マークをクリックしてアカウントを作成してください。