P5007 DDOSvoid 的疑惑

    • 150通过
    • 605提交
  • 题目提供者 DDOSvoid
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 扩展欧几里德,扩欧 逆元
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    DDOSvoid 最近一直很痴迷于树形结构,尤其是可持久化喜羊羊灰太狼套红太狼树,可以 $O(log)$ 维护你想维护的信息。

    但是这只是一个理论数据结构,为了研究其如何实现,DDOSvoid 开始思考树的父亲和儿子之间的关系。

    如果这个数据结构得到实现,那么这个世界就再也没有毒瘤题了

    但毕竟这个问题太难,所以我们先考虑下面的这个问题

    题目描述

    给定一棵以 1 为根的有根树,定义树的一个毒瘤集为一个集合,并且集合中任意两个元素之间不存在祖先与后代关系。

    定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和

    要求给定树的所有毒瘤集的毒瘤指数之和,答案对 100000007 取模。

    但这个问题太难了,所以我们考虑化简。

    因为点的编号跟它毒瘤指数密切相关,所以我们将会再给出一个整数 T,T = 1 表示 i 号点的毒瘤指数为 i,T = 0,表示所有点的毒瘤指数都是 1

    输入输出格式

    输入格式:

    第一行两个整数 n、T,表示这棵树有 n 个节点。

    接下来 n -1 行,每行两个整数 x 和 y,表示有一条边,连接 x 和 y。

    输出格式:

    输出一个整数,表示答案。

    输入输出样例

    输入样例#1: 复制
    5 0
    1 2
    2 3
    2 4
    1 5
    输出样例#1: 复制
    16

    说明

    样例解释:

    10 个集合分别为 $\{1\},\{2\},\{3\},\{4\},\{5\},\{2,5\},\{3,4\}, \{3,5\},\{3,4,5\},\{4,5\}$

    数据范围与约定

    本题采用多测试点捆绑测试

    对于 30 % 的部分分,n <= 15

    另外 20 % 的部分分,n <= 1000000,T = 0

    对于 100 % 的数据,n <= 1000000, T <= 1

    为了方便你理解题意,下面给出毒瘤集的数学定义:

    设一个毒瘤集为$A$,则

    $\forall~i~\in~A$,不存在一个点$j$,使得$j$在从$i$到根节点的简单路径上,且$~j~\in~A$。其中$~i,j~\in~V$,$V$为树的点集。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。