| 227 | |
| 228 | // dp递归版，java会爆栈，C++可以通过 |
| 229 | public static void dp1(int u) { |
| 230 | siz[u] = isKey[u] ? 1 : 0; |
| 231 | sum[u] = 0; |
| 232 | if (isKey[u]) { |
| 233 | far[u] = near[u] = 0; |
| 234 | } else { |
| 235 | near[u] = INF; |
| 236 | far[u] = -INF; |
| 237 | } |
| 238 | for (int e = headv[u]; e > 0; e = nextv[e]) { |
| 239 | dp1(tov[e]); |
| 240 | } |
| 241 | for (int e = headv[u]; e > 0; e = nextv[e]) { |
| 242 | int v = tov[e]; |
| 243 | long len = dep[v] - dep[u]; |
| 244 | costSum += (sum[u] + 1L * siz[u] * len) * siz[v] + sum[v] * siz[u]; |
| 245 | siz[u] += siz[v]; |
| 246 | sum[u] += sum[v] + len * siz[v]; |
| 247 | costMin = Math.min(costMin, near[u] + near[v] + len); |
| 248 | costMax = Math.max(costMax, far[u] + far[v] + len); |
| 249 | near[u] = Math.min(near[u], near[v] + len); |
| 250 | far[u] = Math.max(far[u], far[v] + len); |
| 251 | } |
| 252 | } |
| 253 | |
| 254 | // dp1的迭代版 |
| 255 | public static void dp2(int tree) { |