A15581 | Score of a Tree
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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>0$ , the value of a node becomes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#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$ .
At any integer time $t>0$ , the value of a node becomes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#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$ .
输入格式
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$ .
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$ .
输出格式
Output the sum modulo $10^9+7$ for each test case.
输入输出样例
输入 #1
1 6 1 2 1 3 3 4 3 5 3 6
输出 #1
288
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>2$ , the graph remains unchanged, so $S(t)=0$ for all $t > 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}$ .
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>2$ , the graph remains unchanged, so $S(t)=0$ for all $t > 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}$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted