HDOJ 4661: Message Passing
题意
每个人拥有一个信息,也可以传给另外一个人他拥有的所有信息。现在给定一个联络树,问至少多少次传递可以让所有人拥有所有信息。
题解
可以看出至少要$(n-1)*2$次传递,因为每个人都至少传出一次,传入一次。而怎么可以最少传递呢?我们可以假设根为中心,先将所有信息传递给他,之后再从他传递回来。这里有一点很巧妙,传入和传出的可能种类是一样的,所以我们只需要计算一次传入,平方后便是该点为中心的方案数。
因为子节点必须先传给父节点信息以免漏传,所以传入的方案数是满足一种拓扑排序的。那么可以看我之前的一篇博客,计算拓扑排序对一个点进行计算的。
那么怎么从已知的父节点的$f(root)$传递到子节点$f(v)$呢?
$s(i)$表示以$i$为根节点的子节点数目。
我们假设子节点$s(v)=q$,那么如果子节点变成根节点后,子节点的$s(v)=n$,而原来的父节点$f(u)$变成了$n-q$个子节点数目了。于是通过公式
$f(root)=(f(root)-1)!/s(1)/s(2)/…/s(n)$
我们可以推导出$f(v) = f(u) * s(q)/s(n-q)$
搞定!
AC代码
1 |
|