题解 P7247 【教材运送】

· · 题解

P7247 教材运送

更好的阅读体验

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

题意

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

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

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

## 分析 由于我们的行动一直是随机的，而起点固定是根节点，所以可以把树上的节点分为两部分：根节点与非根节点（每个非根节点都可以视为相同）。 不难想到期望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}$） 总结：遇到关于随机的题可以考虑将同类型的节点放在一起处理，减小状态。 ## 代码 比第二短的代码短了1k左右，可见实现的简单。 想要代码可以私信我。