仓鼠

P3412 仓鼠找sugar II 题解 大水题一个 题目大意 给定你一个树，设 \(f_{u, v}\) 表示在树上随机游走的情况下从 \(u\) 走到 \(v\) 的期望步数，求 \(\displaystyle \frac{\sum_{i = 1}^n \sum_{j = 1}^n f_{i, ......

20231026 P3400 仓鼠窝 题解-单调栈典题 Statement 传送门 输出 01 矩阵中不含 0 的子矩阵的个数。\(n,m \le 3000\) Solution 很妙的做法，典题，于是写了题解。 做法也很简单，就是你枚举每一个节点作为右上角的点的方案数， 发现其实有很多无用的点，比 ......

你也许说得对，但我是真看不懂第一篇题解那个答案式子…… 预处理是差不多的。 设 $f_u$ 表示从 $u\to fa(u)$ 的期望步数，$g_u$ 为 $fa(u)\to u$ 的期望步数，$d_u$ 为 $u$ 的度数。 那么显然有： $$f_u=\frac{1}{d_u}\left(1+\su ......