XOR Tree Codechef solutions Today | Codechef Starters 72 ✅ (100/100) FULL | AC Code ✅| GGTREE

Problem

There is a tree with $N$ vertices, rooted at vertex $1$. Vertex $i$ has the value $A_i$ written on it.

Alice walks along this tree, starting at the root.
When she is at vertex $u$:

• If $u$ has no children, she stops.
• Otherwise, suppose $u$ has $c$ children. She picks one of them at random (each one has a $\frac{1}{c}$ probability of being picked), and then moves to it.

Alice also has a score, defined as follows:

• Let the vertices she visited be $u_1, u_2, \ldots, u_k$
• Then, she will forget exactly one of these $k$ vertices; and her score will be the bitwise xor of the remaining ones.
  • That is, if she chooses to forget vertex $u_i$, then her score is $A_{u_1} \oplus A_{u_2} \oplus \ldots \oplus A_{u_{i-1}} \oplus A_{u_{i+1}} \oplus \ldots \oplus A_{u_{k}}$. Here, $\oplus$ denotes the bitwise xor operation.

Alice wants to maximize her score, and will always choose to forget a vertex optimally to achieve this.

What is Alice's expected final score?

Find the expected value modulo $10^9 + 7$.
That is, the expected value can be written as $\frac{P}{Q}$ for two integers $P, Q$ such that $\gcd(Q, 10^9 + 7) = 1$; print the value of $P\cdot Q^{-1} \pmod{10^9 + 7}$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains a single integer $N$ — the number of vertices of the tree.
  • The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
  • The next $N-1$ lines describe the edges. The $i^{th}$ of these lines contains two space-separated integers $u_i$ and $v_i$, denoting an edge between $u_i$ and $v_i$.

Output Format

For each test case, output on a new line Alice's expected final score.

Constraints

Sample 1:

3
3
3 3 1
1 2
2 3
3
2 2 1
1 2
1 3
4
1 2 3 4
1 2
1 3
1 4

2
2
3

Explanation:

Test case $1$: There's only one final vertex Alice can reach, taking the path $1 \to 2 \to 3$. She will choose to forget one of the $3$'s, for a final score of $3\oplus 1 = 2$.

Test case $3$: There are three leaf nodes, and Alice has a $\frac{1}{3}$ chance of reaching each one.

• If she takes the path $1 \to 2$, her score is $2$ (she will forget $A_1 = 1$)
• If she takes the path $1 \to 2$, her score is $3$ (she will forget $A_1 = 1$)
• If she takes the path $1 \to 2$, her score is $4$ (she will forget $A_1 = 1$)

Her expected score is thus $\frac{1}{3} \cdot (2 + 3 + 4) = 3$.