| 253 | |
| 254 | // dp1的迭代版 |
| 255 | public static void dp2(int tree) { |
| 256 | stacksize = 0; |
| 257 | push(tree, 0, -1); |
| 258 | while (stacksize > 0) { |
| 259 | pop(); |
| 260 | if (e == -1) { |
| 261 | siz[u] = isKey[u] ? 1 : 0; |
| 262 | sum[u] = 0; |
| 263 | if (isKey[u]) { |
| 264 | far[u] = near[u] = 0; |
| 265 | } else { |
| 266 | near[u] = INF; |
| 267 | far[u] = -INF; |
| 268 | } |
| 269 | e = headv[u]; |
| 270 | } else { |
| 271 | e = nextv[e]; |
| 272 | } |
| 273 | if (e != 0) { |
| 274 | push(u, 0, e); |
| 275 | push(tov[e], 0, -1); |
| 276 | } else { |
| 277 | for (int ei = headv[u]; ei > 0; ei = nextv[ei]) { |
| 278 | int v = tov[ei]; |
| 279 | long len = dep[v] - dep[u]; |
| 280 | costSum += (sum[u] + 1L * siz[u] * len) * siz[v] + sum[v] * siz[u]; |
| 281 | siz[u] += siz[v]; |
| 282 | sum[u] += sum[v] + len * siz[v]; |
| 283 | costMin = Math.min(costMin, near[u] + near[v] + len); |
| 284 | costMax = Math.max(costMax, far[u] + far[v] + len); |
| 285 | near[u] = Math.min(near[u], near[v] + len); |
| 286 | far[u] = Math.max(far[u], far[v] + len); |
| 287 | } |
| 288 | } |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | public static void compute() { |
| 293 | for (int i = 1; i <= k; i++) { |