frankchenfu 的博客

frankchenfu 的博客

题解 P1351 【联合权值】

posted on 2018-10-22 12:22:55 | under 题解 |

首先题目给定的是一颗无根树。

由于题目要求的是距离为$2$的所有点对的权值积的和,因此我们可以视作是对于每一个点,与之相邻的所有点两两相乘的和

为什么呢?设相邻点为$v_1,v_2$,这个点为$u$,则对于所有的相邻点,一定有$$\begin{matrix}dis(v_1,v_2)&=&dis(v_1,u)+dis(u,v_2)\\&=&1+1\\&=&2\end{matrix}$$

算法1

所以我们可以对于每一个点枚举相邻的点,然后更新最大值和总和。记每个点度数为$d_i$,则时间复杂度为$O(\displaystyle\sum_{i}^{i\in V}d_i^2)$。

算法2

显然,有同学已经看出来了——菊花图怎么办?复杂度直接就是$O(n^2)$了……

最大积比较简单,每个点只要线性枚举相邻点即可,复杂度是$O(n)$的(与边数同级别),那么总和有类似的方法吗?

答案是肯定的。我们知道:$$\begin{matrix}\displaystyle\sum_{i\in V}^{(u,i)\in E}\displaystyle\sum_{j\in V|j\neq i}^{(u,j)\in E}w_i\cdot w_j&=&\displaystyle\sum_{i\in V}^{(u,i)\in E}\displaystyle\sum_{j\in V}^{(u,j)\in E}w_i\cdot w_j-\displaystyle\sum_{i\in V}w_i^2\\&=&(\displaystyle\sum_{i\in V}w_i)^2-\displaystyle\sum_{i\in V}w_i^2\end{matrix}$$

这玩意中$\sum w_i$和$\sum w_i^2$都可以线性求出,因此我们不需要两两枚举。最终复杂度就降到$O(n)$了。