最小共通祖先

 1type lca struct {
 2	dep []int
 3	par [][]int
 4}
 5
 6func newLowestCommonAncestor(g [][]int, r int) *lca {
 7	n := len(g)
 8	k := 1
 9	for 1<<uint(k) < n {
10		k++
11	}
12	lca := lca{make([]int, n), make([][]int, k)}
13	for i := 0; i < k; i++ {
14		lca.par[i] = make([]int, n)
15	}
16	var dfs func(v, p, d int)
17	dfs = func(v, p, d int) {
18		lca.par[0][v] = p
19		lca.dep[v] = d
20		d++
21		for _, to := range g[v] {
22			if to == p {
23				continue
24			}
25			dfs(to, v, d)
26		}
27	}
28	dfs(r, -1, 0)
29	for i := 0; i < len(lca.par)-1; i++ {
30		for j := 0; j < n; j++ {
31			if lca.par[i][j] == -1 {
32				lca.par[i+1][j] = -1
33			} else {
34				lca.par[i+1][j] = lca.par[i][lca.par[i][j]]
35			}
36		}
37	}
38
39	return &lca
40}
41
42func (a lca) Query(u, v int) int {
43	if a.dep[u] > a.dep[v] {
44		u, v = v, u
45	}
46	for i := len(a.par) - 1; i >= 0; i-- {
47		if (a.dep[v]-a.dep[u])>>uint(i)&1 == 1 {
48			v = a.par[i][v]
49		}
50	}
51	if u == v {
52		return u
53	}
54
55	for i := len(a.par) - 1; i >= 0; i-- {
56		if a.par[i][u] != a.par[i][v] {
57			u = a.par[i][u]
58			v = a.par[i][v]
59		}
60	}
61	return a.par[0][u]
62}
63