P7247 教材运送解题报告

解题报告

---

P7247 教材运送

更好的阅读体验

是我不会的期望题，让我把EI题解复读一遍！

题意

在一棵$n$个点，带点权、边权的树上，不断执行下列行动直到所有节点至少被标记过一次：

设当前起点为$s$（最开始为树根），随机选取一个非$s$节点$t$（不一定要标记过），消耗$a_t\times\sum_{edge\in path(s,t)}v_{edge}$的代价并标记$t$为新的$s$。

求期望代价对$998244353$取模的值。

$1\leqslant n\leqslant 10^6$。

分析

由于我们的行动一直是随机的，而起点固定是根节点，所以可以把树上的节点分为两部分：根节点与非根节点（每个非根节点都可以视为相同）。

不难想到期望dp，于是按套路倒推：设$f_{i,j}(j=0/1)$为还有$i$个节点没有标记，当前节点为根节点/非根节点，接下来所有操作的期望代价。

自然地想到预处理三个量：$x$表示从根节点到随机非根节点的期望代价，$y$表示从随机非根节点到根节点的期望代价，$z$表示从随机非根节点到随机非根节点的代价。

这三个量可以通过一遍dfs求出。

如果我们现在在根节点，还有$i$个没有标记的点，那么有$\frac{i}{n-1}$的概率到没有标记的点，$\frac{n-i-1}{n-1}$的概率到有标记的非根节点，即

$$f_{i,0}=\frac{i}{n-1}f_{i-1,1}+\frac{n-i-1}{n-1}f_{i,1}+x$$

如果我们现在在非根节点，还有$i$个没有标记的节点，那么有$\frac{i}{n-1}$的概率到没有标记的点，有$\frac{1}{n-1}$的概率到根节点，有$\frac{n-1}{n-i-2}$的概率到有标记的非根节点，即

$$f_{i,1}=\frac{i}{n-1}f_{i-1,1}+\frac{1}{n-1}f_{i,0}+\frac{n-i-2}{n-1}f_{i,1}+\frac{1}{n-1}y+\frac{n-2}{n-1}z$$

化简有

$$f_{i,1}=\frac{if_{i-1,1}+f_{i,0}+y+(n-2)z}{i+1}$$

两个式子联立有

$$f_{i,0}=\frac{nif_{i-1,1}+(n-1)(i+1)x+(n-i-1)(y+(n-2)z)}{ni}$$

$$f_{i,1}=\frac{nif_{i-1,1}+(n-1)(x+y+(n-2)z)}{ni}$$

于是$O(n)$递推就好了。（减小常数可以只递推$f_{i,1}$）

总结：遇到关于随机的题可以考虑将同类型的节点放在一起处理，减小状态。

代码

想要代码可以私信我。