| 279 | } |
| 280 | |
| 281 | public static int compute(int x, int y, int v) { |
| 282 | int tmpx = x, tmpy = y; |
| 283 | int[] xpath = new int[] { -INF, INF, 0, 0 }; |
| 284 | int[] ypath = new int[] { -INF, INF, 0, 0 }; |
| 285 | int[] cur = new int[4]; |
| 286 | while (top[x] != top[y]) { |
| 287 | if (dep[top[x]] <= dep[top[y]]) { |
| 288 | query(cur, dfn[top[y]], dfn[y]); |
| 289 | merge(cur, ypath[0], ypath[1], ypath[2], ypath[3]); |
| 290 | clone(ypath, cur); |
| 291 | y = fa[top[y]]; |
| 292 | } else { |
| 293 | query(cur, dfn[top[x]], dfn[x]); |
| 294 | merge(cur, xpath[0], xpath[1], xpath[2], xpath[3]); |
| 295 | clone(xpath, cur); |
| 296 | x = fa[top[x]]; |
| 297 | } |
| 298 | } |
| 299 | if (dep[x] <= dep[y]) { |
| 300 | query(cur, dfn[x], dfn[y]); |
| 301 | merge(cur, ypath[0], ypath[1], ypath[2], ypath[3]); |
| 302 | clone(ypath, cur); |
| 303 | } else { |
| 304 | query(cur, dfn[y], dfn[x]); |
| 305 | merge(cur, xpath[0], xpath[1], xpath[2], xpath[3]); |
| 306 | clone(xpath, cur); |
| 307 | } |
| 308 | int ans = Math.max(Math.max(xpath[3], ypath[2]), ypath[0] - xpath[1]); |
| 309 | x = tmpx; |
| 310 | y = tmpy; |
| 311 | while (top[x] != top[y]) { |
| 312 | if (dep[top[x]] <= dep[top[y]]) { |
| 313 | add(dfn[top[y]], dfn[y], v, 1, n, 1); |
| 314 | y = fa[top[y]]; |
| 315 | } else { |
| 316 | add(dfn[top[x]], dfn[x], v, 1, n, 1); |
| 317 | x = fa[top[x]]; |
| 318 | } |
| 319 | } |
| 320 | add(Math.min(dfn[x], dfn[y]), Math.max(dfn[x], dfn[y]), v, 1, n, 1); |
| 321 | return ans; |
| 322 | } |
| 323 | |
| 324 | public static void main(String[] args) throws IOException { |
| 325 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); |