CF1777D.Score of a Tree

You are given a tree of $n$ nodes, rooted at $1$. Every node has a value of either $0$ or $1$ at time $t=0$.

At any integer time $t \gt 0$, the value of a node becomes the bitwise XOR of the values of its children at time $t - 1$; the values of leaves become $0$ since they don't have any children.

Let $S(t)$ denote the sum of values of all nodes at time $t$.

Let $F(A)$ denote the sum of $S(t)$ across all values of $t$ such that $0 \le t \le 10^{100}$, where $A$ is the initial assignment of $0$s and $1$s in the tree.

The task is to find the sum of $F(A)$ for all $2^n$ initial configurations of $0$s and $1$s in the tree. Print the sum modulo $10^9+7$.

给你一棵包含 $n$ 个节点的树，根节点为 $1$。在时刻 $t=0$，每个节点的值为 $0$ 或 $1$。

在任意整数时刻 $t > 0$，一个节点的值变为其所有子节点在时刻 $t-1$ 的值的按位异或（XOR）；由于叶子节点没有子节点，其值变为 $0$。

令 $S(t)$ 表示时刻 $t$ 所有节点的值之和。

令 $F(A)$ 表示对所有满足 $0 \le t \le 10^{100}$ 的整数 $t$，$S(t)$ 的总和，其中 $A$ 是树中初始的 $0$ 和 $1$ 的赋值方案。

任务是：对树的所有 $2^n$ 种初始 $0/1$ 配置 $A$，求 $F(A)$ 的总和。请输出该总和对 $10^9+7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of nodes in the tree.

The next $n-1$ lines of each test case contain two integers each — $u$, $v$ indicating an edge between $u$ and $v$ ($1 \le u, v \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示树中节点的数量。

每个测试用例的接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 与 $v$ 之间存在一条边（$1 \le u, v \le n$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

Output the sum modulo $10^9+7$ for each test case.

对每个测试用例，输出结果对 $10^9+7$ 取模后的和。

Let us find $F(A)$ for the configuration $A = [0,1,0,0,1,1]$ ($A[i]$ denotes the value of node $i$). Initially (at $t = 0$) our tree is as shown in the picture below. In each node, two values are shown: the number and the value of this node. $S(0)$ for this configuration is $3$.

At $t = 1$ the configuration changes to $[1,0,0,0,0,0]$. The tree looks as shown below. $S(1) = 1$.

At $t = 2$ the configuration changes to $[0,0,0,0,0,0]$. The tree looks as shown below. $S(2) = 0$.

For all $t \gt 2$, the graph remains unchanged, so $S(t)=0$ for all $t \gt 2$. So, for the initial configuration $A = [0,1,0,0,1,1]$, the value of $F(A) = 3 + 1 = 4$.

Doing this process for all possible $2^{6}$ configurations yields us an answer of $\textbf{288}$.

我们来计算配置 $A = [0,1,0,0,1,1]$（其中 $A[i]$ 表示节点 $i$ 的值）对应的 $F(A)$。初始时刻（$t = 0$）时，树结构如下图所示。每个节点中显示两个值：节点编号和该节点的值。此配置下，$S(0) = 3$。

在 $t = 1$ 时刻，配置变为 $[1,0,0,0,0,0]$。此时树结构如下图所示，$S(1) = 1$。

在 $t = 2$ 时刻，配置变为 $[0,0,0,0,0,0]$。此时树结构如下图所示，$S(2) = 0$。

对所有 $t > 2$，图结构保持不变，因此对所有 $t > 2$ 均有 $S(t) = 0$。于是，对于初始配置 $A = [0,1,0,0,1,1]$，有 $F(A) = 3 + 1 = 4$。

对全部 $2^{6}$ 种可能的配置执行上述过程，最终得到答案为 $\textbf{288}$。