2012年4月27日 星期五

tioj 1592 觸手 Tentacles

這題是有趣的題目

有很漂亮的O(n)解法

 -> dfs兩次

第一次求出該節點以下的 1. 和, 2. 平方和, 3. 節點數

接下來就可以求出每個節點的距離平方和了

因為(距離加一)平方=距離平方+2*距離和+1

http://codepad.org/lt6iItAv

2 則留言:

  1. 有 sort 就 nlogn ?
    還是你沒sort?

    回覆刪除
    回覆
    1. 可以不用sort啦XD

      可是其實我有,反正code不用改多少XP

      刪除