前置

• 1072. 树的最长路径
• 1171. 距离

思路

定理：

1. 边权非负时，树的直径求法：任选一个点 $a$，找到离它最远的点 $b$，再找到离 $b$ 最远的点 $c$，则 $b \sim c$ 是一条直径。
2. 树上任意两点 $a, b$ 间距离 $dist(a, b) = depth(a) + depth(b) - 2 \times depth(lca(a, b))$，其中 $depth(x)$ 是 $x$ 到根的距离，$lca(a, b)$ 是 $a, b$ 两点的最近公共祖先。

性质：

若上一次树的直径是 $A \sim B$，现在要在 $u$ 下增加两个子节点 $x, y$，若直径变大，则新直径的一个端点必然是 $x$ 或 $y$。$x, y$ 等价，下面仅考虑 $x$。

1. 若 $dist(A, B) < max(dist(A, x), dist(B, x))$，由于未添加节点前 $u$ 到任何节点的距离小于等于 $dist(A, B)$，因此 $x$ 到任何节点的距离最多比 $u$ 到任何节点的距离多 $1$，因此 $dist(A, x) \le dist(A, B) + 1$。不妨设此时 $dist(A, x) > dist(A, B)$，则 $dist(A, x) = dist(A, B) + 1$。由于 $x$ 到任何节点的距离不可能超过 $dist(A, B) + 1$，所以此刻 $A \sim x$ 是一条新直径。同理，若 $dist(B, x) > dist(A, B)$，$B \sim x$ 是一条新直径。
2. 若 $dist(A, B) \ge max(dist(A, x), dist(B, x))$，则距离 $A$ 最远的点是 $B$，且距离 $B$ 最远的点是 $A$，因此 $A \sim B$ 仍是直径。

时间复杂度：$mlog(n)$，其中 $m$ 为询问次数，$n$ 为最大节点数。

package main

import (
  "bufio"
  "fmt"
  "os"
)

const N, M = 1000010, 20

var (
  rd = bufio.NewReader(os.Stdin)
  wt = bufio.NewWriter(os.Stdout)

  f [N][M]int
  d [N]int
)

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

func lca(a, b int) int {
  if d[a] < d[b] {
    a, b = b, a
  }

  for k := M - 1; k >= 0; k-- {
    if d[f[a][k]] >= d[b] {
      a = f[a][k]
    }
  }
  if a == b {
    return a
  }

  for k := M - 1; k >= 0; k-- {
    if f[a][k] != f[b][k] {
      a, b = f[a][k], f[b][k]
    }
  }
  return f[a][0]
}

func main() {
  defer wt.Flush()

  n := 4
  for i := 2; i <= n; i++ {
    d[i], f[i][0] = 1, 1
  }
  A, B, L := 2, 3, 2

  dist := func(a, b int) int {
    return d[a] + d[b] - (d[lca(a, b)] << 1)
  }

  var m int
  fmt.Fscanln(rd, &m)
  for i := 0; i < m; i++ {
    var u int
    fmt.Fscanln(rd, &u)
    x, y := n + 1, n + 2; n += 2

    d[x] = d[u] + 1; d[y] = d[x]
    f[x][0], f[y][0] = u, u
    for k := 1; k < M; k++ {
      f[x][k] = f[f[x][k - 1]][k - 1]
      f[y][k] = f[f[y][k - 1]][k - 1]
    }

    d1, d2 := dist(A, x), dist(B, x)
    if d1 == L + 1 {
      B = x
      L++
    } else if d2 == L + 1 {
      A = x
      L++
    }

    fmt.Fprintln(wt, L)
  }
}