跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0302. #6240. 仙人掌

  • ID: 308
  • 传统题
  • 1000ms
  • 986MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 图论
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#6240. 仙人掌

题目描述

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在给你一个 个点, 条边的仙人掌,你想要求出对其点分治的期望复杂度,点分治过程如下:

  • 加上当前连通块大小。

  • 从当前连通块中随机选择一个点,将其删除,并删除它连出去的所有边。

  • 对剩下的每个连通块递归调用这个函数。

请求出 的期望,答案模 。

输入格式

第一行两个整数 。

接下来 行,每行两个整数 描述一条边。

输出格式

一行一个整数表示答案。

样例

样例输入

5 4
1 2
1 3
1 4
1 5

样例输出

13

数据范围与提示

对于的数据,有。

有四个子任务:

Subtask 1():。

Subtask 2():。

Subtask 3():。

Subtask 4():无其他限制。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 206 题。保留原作者与原赛事署名。