题解 「2019五校联考-镇海1」一棵树

djh0314 · 2023-11-10 08:48:35 · 个人记录

题意

一棵 n 个结点的树，根节点为 1，结点 i 的父亲是 f_i。f_1=f_0=0。对于每一个整数 i，假如 f_{f_i} 不为 0，那么就将 f_{f_i} 与 i 连上一条边。从每一个结点，每次随机向相邻的结点走。问每个结点期望走多少步才能走到根。

对于 60\%，n\le 300。
对于 100\%，n\le 2000。

分析

对于 60\% 的数据，我们可以暴力建图，然后用高斯消元即可。

对于 100\% 的数据，有两种解法。

Solution1

可以用稀疏矩阵优化，可以讲时间复杂度优化，玄学优化可过。

Solution2

我们将儿子的权值在父亲处消耗完，用 O(n) 解决即可。