#Y. 『GROI-R1』继续深潜，为了同一个梦想

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \

Type: RemoteJudge

1000~2000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

玘正在折叠床脚几件刚洗净的白衬衫，他注意到身后的声响，向右后转头看去。

以为是“外面的家伙”的他并没有刻意去遮掩自己的右眼——毕竟学院里的人不可能进来。

他看见了那个紫眸的少年；当然寒也看见了那一瞬间的鲜红。

「你什么都没看见。」

玘装作欣赏窗外的晚霞。

题目描述

「世上没有无价的情报，」玘露出一丝满意的微笑。

「你懂我的意思吧？」

寒收回手。

玘给出了他留给寒的题。

既然紫堇和彼岸花给予了我们异色的瞳孔，我们理所应当是连接在一起的。我称一棵树上的一个点集是“连接的”，当且仅当树上存在一条链能够覆盖这个点集并且这个集合大小不小于 $2$ 。我们是独一无二的，可是你知道，一棵树，总是连起来的啊。

「然后呢？」

「现在，你需要告诉我每个点被多少个这样的点集所包含。」

玘飘然而去。

湖底之城那封存已久的记忆，被彼岸花和紫堇的力量，揭开了封印的一角。

输入格式

第一行一个正整数 $n$ 表示这棵树有 $n$ 个点编号为 $1\sim n$ 。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 描述一条边。

输出格式

为了防止输出量过大，本题采用以下的输出方式。

设 $ans_i$ 为包含 $i$ 号节点的连接的集合的个数对 $10^9+7$ 取模得到的值，你需要输出 $\operatorname{xor}_{i=1}^n ans_i\times i$ 的值。注意这里没有取模运算。

提示

样例解释

连接的集合有以下一些：

$\{1,2\}$
$\{1,3\}$
$\{1,4\}$
$\{2,3\}$
$\{2,4\}$
$\{3,4\}$
$\{1,2,3\}$
$\{1,2,4\}$
$\{2,3,4\}$

如 $\{1,3,4\}$ 就不是一个连接的集合，因为你找不出一条链使得 $\{1,3,4\}$ 为它的子集。

其中 $1,2,3,4$ 号节点分别在 $5,6,5,5$ 个集合中出现。通过计算可得 $\operatorname{xor}_{i=1}^n ans_i\times i=18$ 。

数据范围

本题采用捆绑测试。

子任务编号	数据范围	特殊性质	分值	时间限制
$\text{Subtask1}$	$n\le20$		$15$	$\text{1s}$
$\text{Subtask2}$	$n\le100$		$15$
$\text{Subtask3}$	$n\le3\times 10^3$		$20$
$\text{Subtask4}$	$n\le5\times10^5$	$\text{A}$	$15$	$\text{2s}$
$\text{Subtask5}$	$n\le5\times10^5$		$35$	$\text{2s}$

特殊性质 $\text{A}$ ：保证树退化成一条链。

对于 $100\%$ 的数据 $1\le u,v\le n\le5\times10^5$ 。

国庆提高组30题(1~3号)

Not Attended

Status: Done
Rule: IOI
Problem: 28
Start at: 2024-9-29 17:00
End at: 2024-10-8 1:00
Duration: 200 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 55

#Y. 『GROI-R1』继续深潜，为了同一个梦想

『GROI-R1』继续深潜，为了同一个梦想

题目背景

题目描述

输入格式

输出格式

提示

国庆提高组30题(1~3号)

Status

Development

Support

#Y. 『GROI-R1』 继续深潜，为了同一个梦想

『GROI-R1』 继续深潜，为了同一个梦想

题目背景

题目描述

输入格式

输出格式

提示

国庆提高组30题(1~3号)

Status

Development

Support

Don't have an account?

SIGN IN

#Y. 『GROI-R1』继续深潜，为了同一个梦想

『GROI-R1』继续深潜，为了同一个梦想