| 题目名称 | 2285. [HZOI 2015]疯狂的粉刷匠 |
|---|---|
| 输入输出 | F_Tree.in/out |
| 难度等级 | ★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：10， 通过率：70% | ||||
 AntiLeaf |
100 | 0.662 s | 23.20 MiB | C++ |
 FoolMike |
100 | 0.826 s | 40.34 MiB | C++ |
 神利·代目 |
100 | 1.738 s | 26.99 MiB | C++ |
 _Horizon |
100 | 2.132 s | 34.65 MiB | C++ |
 Aglove |
100 | 2.189 s | 34.65 MiB | C++ |
 0 |
100 | 2.240 s | 31.16 MiB | C++ |
 Zayin |
100 | 2.472 s | 53.72 MiB | C++ |
|
神利·代目 |
40 | 1.741 s | 26.99 MiB | C++ |
|
Zayin |
40 | 2.452 s | 53.72 MiB | C++ |
|
_Horizon |
0 | 2.275 s | 34.65 MiB | C++ |
| 关于 疯狂的粉刷匠 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
http://www.cnblogs.com/joyouth/p/5437444.html
本蒟蒻的题解报告，欢迎各路神犇来踩 Aglove
2016-04-27 08:23
1楼
| ||||
【题目描述】
有一天粉刷匠接到了一个任务，要求他给一棵树染色
不过这只粉刷匠很疯狂，他每次会等概率的选取树上的一个联通点集，并给这个联通点集染色
现在粉刷匠想要知道，他第一次染色后树上期望有多少个点被染色
为了防止精度误差，设答案形式为a/b，设b在模1e9+7意义下的逆元为c
请输出(a*c)%(1e9+7)的值
【输入格式】
第一行n表示节点总数
之后n-1行每行两个数u，v描述一条边的两个端点
n<=1000000
【输出格式】
输出题目要求的答案
【样例输入】
输入1：
2
2 1
输入2：
3
2 1
3 1
【样例输出】
输出1：333333337
输出2：666666673
【提示】
样例解释：
样例1中，一共有3种可能的联通点集，大小分别为1,1,2，所以答案为4/3 按题意输出即可
样例2中，一共有6中可能的联通点集，大小分别为1,1,1,2,2,3，所以答案为10/6 按题意输出即可
联通点集为点全集的一个子集且这个子集在树上是一个完整的联通块