9 条评论
-
Platypus LV 9 @ 2014-11-14 20:34:20
NOIP过了之后整个Vijos都冷清了 =.=-
@ 2014-11-14 20:57:01
是的
-
-
@ 2014-11-10 06:46:33
今年noip好简单... 随便水水就可以600.
-
@ 2014-11-11 19:32:15
orz orz
-
@ 2014-11-14 20:18:55
orz orz
-
@ 2014-11-14 20:33:15
orz orz
-
@ 2014-11-22 20:39:21
orz orz
-
-
@ 2014-11-08 15:45:46
就第三不会
-
@ 2014-11-08 15:27:06
[本蒟蒻做法]
首先DFS一遍
这一遍DFS能干很多事情，包括：
（1）记录每个点的孙子之和以及MAX
（2）记录每个点的儿子之和和儿子的平方和。
之后我们发现一个结论叫做2Sigma(Wi·Wj) = Sigma(Wi) ^ 2 - Sigma(Wi ^ 2)
于是之前求的平方和就派上用场了。
再之后枚举每个点求MAX和SUM即可时间复杂度：DFS是O(N)的，枚举是O(N)的，所以一共是O(N)的
-
@ 2014-11-08 15:38:17
orz
-
@ 2014-11-15 07:37:08
这样应该不需要建树了吧...
vector或者邻接表记录跟与每个点相邻的所有点 统计他们平方的和减平方和
应该是一样的 -
@ 2014-11-15 15:38:35
+1
-
-
@ 2014-11-08 15:11:04
实在想不出 暴力就交上去了
-
@ 2014-11-08 14:26:50
话说 T2不是有各种水过的算法嘛……遍历一遍或者统计邻居的和都行嘛……
-
@ 2014-11-08 14:23:33
我不会
-
@ 2014-11-08 14:20:36
蒟蒻表示看到考场里有人提前一小时提交 顿时吓傻了QAQ
-
@ 2014-11-08 13:57:14
题目好水。。。。虽然我不会，。。。。
- 1
