{"problem":{"name":"『GROI-R1』 继续深潜，为了同一个梦想","description":{"content":"「世上没有无价的情报，」玘露出一丝满意的微笑。 「你懂我的意思吧？」 寒收回手。 玘给出了他留给寒的题。 > 既然紫堇和彼岸花给予了我们异色的瞳孔，我们理所应当是连接在一起的。我称**一棵树上的一个点集是“连接的”**，当且仅当**树上存在一条链能够覆盖这个点集并且这个集合大小不小于 $2$**。我们是独一无二的，可是你知道，一棵树，总是连起来的啊。 「然后呢？」 「现在，你需要告诉我","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8973"},"statements":[{"statement_type":"Markdown","content":"「世上没有无价的情报，」玘露出一丝满意的微笑。\n\n「你懂我的意思吧？」\n\n寒收回手。\n\n玘给出了他留给寒的题。\n\n> 既然紫堇和彼岸花给予了我们异色的瞳孔，我们理所应当是连接在一起的。我称**一棵树上的一个点集是“连接的”**，当且仅当**树上存在一条链能够覆盖这个点集并且这个集合大小不小于 $2$**。我们是独一无二的，可是你知道，一棵树，总是连起来的啊。\n\n「然后呢？」\n\n「现在，你需要告诉我每个点被多少个这样的点集所包含。」\n\n玘飘然而去。\n\n湖底之城那封存已久的记忆，被彼岸花和紫堇的力量，揭开了封印的一角。\n\n## Input\n\n第一行一个正整数 $n$ 表示这棵树有 $n$ 个点编号为 $1\\sim n$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$ 描述一条边。\n\n## Output\n\n为了防止输出量过大，本题采用以下的输出方式。\n\n设 $ans_i$ 为包含 $i$ 号节点的连接的集合的个数对 $10^9+7$ 取模得到的值，你需要输出 $\\operatorname{xor}_{i=1}^n ans_i\\times i$ 的值。注意这里没有取模运算。\n\n[samples]\n\n## Background\n\n玘正在折叠床脚几件刚洗净的白衬衫，他注意到身后的声响，向右后转头看去。\n\n以为是“外面的家伙”的他并没有刻意去遮掩自己的右眼——毕竟学院里的人不可能进来。\n\n他看见了那个紫眸的少年；当然寒也看见了那一瞬间的鲜红。\n\n「你什么都没看见。」\n\n玘装作欣赏窗外的晚霞。\n\n## Note\n\n**样例解释**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/rl9wkbww.png)\n\n**连接**的集合有以下一些：\n- $\\{1,2\\}$\n- $\\{1,3\\}$\n- $\\{1,4\\}$\n- $\\{2,3\\}$\n- $\\{2,4\\}$\n- $\\{3,4\\}$\n- $\\{1,2,3\\}$\n- $\\{1,2,4\\}$\n- $\\{2,3,4\\}$\n\n如 $\\{1,3,4\\}$ 就不是一个连接的集合，因为你找不出一条链使得 $\\{1,3,4\\}$ 为它的子集。\n\n其中 $1,2,3,4$ 号节点分别在 $5,6,5,5$ 个集合中出现。通过计算可得 $\\operatorname{xor}_{i=1}^n ans_i\\times i=18$。\n\n**数据范围**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 数据范围 | 特殊性质 | 分值 | 时间限制 |\n| :----------: | :----------: | :----------: | :----------: | :-: |\n| $\\text{Subtask1}$ | $n\\le20$ | | $15$ | $\\text{1s}$ |\n| $\\text{Subtask2}$ | $n\\le100$ | | $15$  | $\\text{1s}$ |\n| $\\text{Subtask3}$ | $n\\le3\\times 10^3$ | | $20$ | $\\text{1s}$ |\n| $\\text{Subtask4}$ | $n\\le5\\times10^5$ | $\\text{A}$ | $15$ | $\\text{2s}$ |\n| $\\text{Subtask5}$ | $n\\le5\\times10^5$ | | $35$ | $\\text{2s}$ |\n\n特殊性质 $\\text{A}$：保证树退化成一条链。\n\n对于 $100\\%$ 的数据 $1\\le u,v\\le n\\le5\\times10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8973","tags":["动态规划 DP","数学","图论","线段树","点分治","O2优化","树形 DP"],"sample_group":[["4\n1 2\n2 3\n2 4","18"]],"created_at":"2026-03-03 11:09:25"}}