game
簡而言之，這題就是將「樹上最長路, 樹的直徑」這個經典題做了以下的修改：

從邊權變為點權
權重可以為負
從樹變成水母（點數和邊數一樣的連通圖，恰好只有一個環）
比起正確的作法，值得一提的是因為條件的設定這題存在許多錯誤的做法：

2次BFS找最長路 在只有樹的測資也是錯的，因為有負權重
floyd warshall 是錯的，因為存在正環。同理，bellman-ford 也會因為正環出錯
dijkstra 也會錯，因為有正權（diskstra不能做負權最短路，或正權最長路）
這些演算法的限制十分容易混淆，而且比賽中一旦陷入錯誤的做法通常會很難跳脫。 筆者這裡建議大家學演算法的時候要多留意證明的過程，以避免陷入用錯誤演算法而無法跳脫的死胡同。

樹的最長路
在挑選某個點作為 root 以後可以 DP 紀錄兩個表格:

down[i]: 以 i 為起點，往下到某個點的最長路徑
dp[i]: 以 i 為 root 的子樹中最長的路徑
其中 dp[i] 可以由下面幾種狀況轉移過來:

狀況1: 最長路不經過 i
dp[i] = dp[c]，c 是 i 的某個兒子
狀況2: 最長路以 i 為起點
dp[i] = w[i] + down[c], c 是 i 的某個兒子
狀況3: 最常路中間經過 i
dp[i] = w[i] + down[c1] + down[c2], c1, c2 是 i 的某兩個兒子
可以在線性時間內求出每棵子樹的最長路。

水母最長路
把環上的每個點看成是很多棵樹的 root 串聯起來，依照最長路經過的非樹根節點可以分類成兩種情況:

是某棵樹上的最長路
是某棵樹上的一條由下往上的路徑 + 環上某些邊 + 另一棵樹由上往下的路徑
(1) 的部分可以對每棵樹做一次 DP 在線性求出來， (2) 的部分可以算出每棵樹 down 值後在環上再做一次 DP，DP 的值可以用前綴和 + deque 或 set 維護。 最快的作法一樣可以在線性的時間算完。