1806E

`2023-07-19 10:59:11` 思路来源于题解:https://www.luogu.com.cn/problem/solution/CF1806E 算法：根号分治+记忆化搜索。 因为每一个查询都是同层的，我们可以只记忆层数少的（小于$\sqrt n$）,对于层数多的层，如果大于$ \sq ......

## 题目大意 给你一棵树，然后定义一个函数 $ f(x,y) $，接下来给你 $ q $ 组询问 $x_{i},y_{i}$，让你求每一次的 $ f(x_{i},y_{i})$。 ## 分析 首先我们尝试根据这个函数的定义暴力求值，代码实现如下。 ```cpp ll BFquery(int g,i ......

题面 看起来是个 DS 题，事实上是个乱搞题，做法挺多的。由于它给的这个结构看起来就不好优化，所以考虑随机化。 由于两个点到达 LCA 后剩下的贡献就是 LCA 到根的每个点权值的平方，这部分可以 $O(n)$ 预处理，所以只需要考虑两个点之间的路径所产生的贡献。 在树上随机撒 $\sqrt n$ ......

题面 看起来是个 DS 题，事实上是个乱搞题，做法挺多的。由于它给的这个结构看起来就不好优化，所以考虑随机化。 由于两个点到达 LCA 后剩下的贡献就是 LCA 到根的每个点权值的平方，这部分可以 $O(n)$ 预处理，所以只需要考虑两个点之间的路径所产生的贡献。 在树上随机撒 $\sqrt n$ ......