【寒假作业】【NOIP2014】联合权值

首先显而易见的是总的联合权值就是每一个点周边点两两相乘的权值和。。

显然不能枚举每个点周围的点。。那么可以预处理出每个点周围点的权值和,这个和的平方多了周边每个点的权值平方和,那么只要在总的权值和里减去每个点的度*每个点的权值平方就可以了。

最大值的话只要记下每个点周围点里权值最大和第二大的点,最后比较一下即可。

复杂度O(n)。

【代码很短,网上好多代码都好长←_←还写什么树形DP DFS BFS啥的

说点什么

2 评论 在 "【寒假作业】【NOIP2014】联合权值"

提醒
排序:   最新 | 最旧 | 得票最多
游客

树分治!

wpDiscuz