前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-25:给定数组father大小为N,表示一共有N个节点,father[i] = j 表示点i的父亲是点j, fa

2021-08-25:给定数组father大小为N,表示一共有N个节点,father[i] = j 表示点i的父亲是点j, fa

作者头像
福大大架构师每日一题
发布2021-09-03 15:25:43
3360
发布2021-09-03 15:25:43
举报

2021-08-25:给定数组father大小为N,表示一共有N个节点,father[i] = j 表示点i的父亲是点j, father表示的树一定是一棵树而不是森林,queries是二维数组,大小为M*2,每一个长度为2的数组都表示一条查询,[4,9], 表示想查询4和9之间的最低公共祖先…,[3,7], 表示想查询3和7之间的最低公共祖先…,tree和queries里面的所有值,都一定在0~N-1之间。返回一个数组ans,大小为M,ans[i]表示第i条查询的答案。

福大大 答案2021-08-25:

树链剖分。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import "fmt"

func main() {
    father := []int{2, 3, 3, 3, 2, 1}
    queries := [][]int{
        []int{2, 0},
        []int{0, 4},
        []int{4, 5},
        []int{1, 0},
        []int{2, 2},
    }
    ret := query3(father, queries)
    fmt.Println(ret)
}

// 在线查询最优解 -> 树链剖分
// 空间复杂度O(N), 支持在线查询,单次查询时间复杂度O(logN)
// 如果有M次查询,时间复杂度O(N + M * logN)
func query3(father []int, queries [][]int) []int {
    tc := NewTreeChain(father)
    M := len(queries)
    ans := make([]int, M)
    for i := 0; i < M; i++ {
        // x y ?
        // x x x
        if queries[i][0] == queries[i][1] {
            ans[i] = queries[i][0]
        } else {
            ans[i] = tc.lca(queries[i][0], queries[i][1])
        }
    }
    return ans
}

type TreeChain struct {
    n    int
    h    int
    tree [][]int
    fa   []int
    dep  []int
    son  []int
    siz  []int
    top  []int
}

func NewTreeChain(father []int) *TreeChain {
    ans := &TreeChain{}
    ans.initTree(father)
    ans.dfs1(ans.h, 0)
    ans.dfs2(ans.h, ans.h)
    return ans
}

func (this *TreeChain) initTree(father []int) {
    this.n = len(father) + 1
    this.tree = make([][]int, this.n)
    this.fa = make([]int, this.n)
    this.dep = make([]int, this.n)
    this.son = make([]int, this.n)
    this.siz = make([]int, this.n)
    this.top = make([]int, this.n)
    this.n--
    cnum := make([]int, this.n)
    for i := 0; i < this.n; i++ {
        if father[i] == i {
            this.h = i + 1
        } else {
            cnum[father[i]]++
        }
    }
    this.tree[0] = make([]int, 0)
    for i := 0; i < this.n; i++ {
        this.tree[i+1] = make([]int, cnum[i])
    }
    for i := 0; i < this.n; i++ {
        if i+1 != this.h {
            cnum[father[i]]--
            this.tree[father[i]+1][cnum[father[i]]] = i + 1
        }
    }
}

func (this *TreeChain) dfs1(u int, f int) {
    this.fa[u] = f
    this.dep[u] = this.dep[f] + 1
    this.siz[u] = 1
    maxSize := -1
    for _, v := range this.tree[u] {
        this.dfs1(v, u)
        this.siz[u] += this.siz[v]
        if this.siz[v] > maxSize {
            maxSize = this.siz[v]
            this.son[u] = v
        }
    }
}

func (this *TreeChain) dfs2(u int, t int) {
    this.top[u] = t
    if this.son[u] != 0 {
        this.dfs2(this.son[u], t)
        for _, v := range this.tree[u] {
            if v != this.son[u] {
                this.dfs2(v, v)
            }
        }
    }
}

func (this *TreeChain) lca(a int, b int) int {
    a++
    b++
    for this.top[a] != this.top[b] {
        if this.dep[this.top[a]] > this.dep[this.top[b]] {
            a = this.fa[this.top[a]]
        } else {
            b = this.fa[this.top[b]]
        }
    }

    return twoSelectOne(this.dep[a] < this.dep[b], a, b) - 1
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class23/Code01_LCATarjanAndTreeChainPartition.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档