给给

[编程题]给给

热度指数：1 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵树，一共执行k次操作，每次随机选择两个点，并将它们这条唯一路径上的点都染上色
求所有操作结束后被染上色的点的个数的期望值
答案对10⁹+7取模
注：选择的两个点是无序地选择的，(1,2) 和 (2,1) 是同一个方案。

输入描述:

第一行两个整数n,k
之后n-1行，每行两个整数u,v，表示u,v之间有一条边相连

输出描述:

一行一个整数表示答案

示例1

输入

2 1
1 2

输出

333333337

说明

显然选择方案只有三种，即(1,1),(2,2),(1,2)
前两者只会染上一个点，后一者会染上两个点
因此

备注:

数据范围
0 ≤ k ≤ 10¹⁸
1 ≤ n ≤ 5 x 10⁶
有10分的数据，保证n=10,k=100
有10分的数据，保证n=1000000,k=100000000000000128，且树退化成了一条链
注：为了不被卡读入，请找个快速读入的板子

算法知识视频讲解

憕

发表于 2022-11-10 11:07:24

线性期望dp 因为是求最终被染色的节点数，对于每个节点分开考虑如果第i个节点被在k次操作里染色的概率为p，则它的对期望的贡献为 pi*1；所以总的期望E = 所有节点被选的的概率之和。对于第i个节点被选的概率不好求，但是可以求它的对立事件，在k次操作里面都不被选的概率q，所以p = 1-q；一次展开全文