1 条题解

  • -1
    @ 2024-5-31 14:51:12
    思路

    容易想到,能够管理员工a1,a2,...,am的人为lca(a1,a2,...,am)a_1 ,a_2,...,a_m的人为lca(a_1 ,a_2,...,a_m)以及该lcalca的祖先节点,题目还要求编号最大,也就是从根到该lcalca路径上所有点的编号最大值,这个可以提前预处理,设mxID[u]mxID[u]表示从根到uu路径上所有节点编号的最大值,对于每组询问,首先求出所有参与的员工的lcalca,接着输出mxID[lca]mxID[lca]即可,求lcalca比较常用的有倍增法或树链剖分等。

    参考代码

    image image

    • 1

    [GESP202312 八级] 大量的工作沟通

    信息

    ID
    584
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    15
    已通过
    6
    上传者