题解 P1351 【联合权值】

首先题目给定的是一颗无根树。 由于题目要求的是距离为$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)$了。