Ali has an interview with a big company again, the interviewer gave him a problem that Ali can't solve, so he asked you to help him as he is curious about the solution
The problem goes as follows:
Given two weighted trees, let's define:-
Your task is to find the sum of all triples' paths across all triples, as the answer is very large, print it modulo $10^9 + 7$.
The first line contains a single integer $n$ $(2 \le n \le 10^{5})$. --- the number of nodes in the tree.
Then following $n$ - $1$ lines describe the edges of the first tree, each of them contains three integers $u$,$v$,$w$ ($1$ $\le$ $u$, $v$ $\le$ $n$), $(1 \le w < 2^{30})$.
Then another $n - 1$ lines describe the edges of the second tree, each of them contains three integers $u$,$v$,$w$ ($1$ $\le$ $u$, $v$ $\le$ $n$), $(1 \le w < 2^{30})$.
Print one integer representing the answer as described in the statement.
| Input | Output |
|---|---|
3 1 2 1 2 3 2 1 2 1 1 3 2 Copy
|
38 Copy
|
First, let's root each tree at any node, we can prove that $dist(u, v)$ is equal to $dist(root, u)$ $\oplus$ $dist(root, v)$.
We will assume that the root is 1 in both trees. the value of the triple path $(u,v,p)$ is equal to:
$dist1(1, u)$ $\oplus$ $dist1(1, v)$ $\oplus$ $dist2(1, v)$ $\oplus$ $dist2(1, p)$
Now, Let's define $f(i)$ as how many triple paths that have $1$ in the $i^{th}$ bit.
So the answer will be
$\quad$ $\quad$ $\sum_{i=0}^{29} 2^{i} \times f(i)$ $\quad$ (mod $10^9+7$)
We can calculate $f(i)$ using dynamic programing in $O(n)$.
For each node try to pack it as u, v, or p, and keep the state of the $i-th$ bit in the xor.