洛谷P1351 - 联合权值

 题解 / 洛谷
被浏览

由题意得一个点对的联合权值是它们的点权相乘,而 2 个点形成点对的条件是距离为 2。

于是我们可以通过枚举这 2 个节点的公共点来算出以这个点为中心的权值和。

但是先枚举中心点再枚举其相邻的节点时间复杂度达到了$O(n^3)$,我们不能承受。

经过观察发现,对于特定的点,它都要乘上除自己以外的所有点权,再相加。然后我们就可以先处理出点权和,统计答案的时候把自己减去即可。