最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 命中目标

    正文概述 陈老师   2026-01-20 15:15:30  

    题目描述

    给定一棵以节点 11 为根的包含 nn 个节点的树。对于每个节点 ii(2≤i≤n2 ≤ i ≤ n),其父节点记为 fif_i,表示节点 ii 与 fif_i 之间有一条边。初始时,一个棋子位于节点 11。

    本题中,时间从 11 开始离散递增。共有 kk 个互不重叠的时间区间 [li, ri][l_i,\ r_i],每个区间内会有一个目标出现在节点 uiu_i。你可以在任意时刻(包括时刻 00)切断任意数量的树边(允许多次操作),且切断的边将永久移除。

    在任意时刻:

    1. 若当前时刻处于某个 [li, ri][l_i,\ r_i] 区间内(即目标活跃),且
    2. 棋子与目标位于同一连通分量中,且
    3. 棋子当前不在目标节点上,

    则棋子会沿着唯一简单路径向目标节点移动一步。若棋子到达目标节点(或初始时已在目标节点),则视为一次命中。

    你的任务是:通过策略性切断边,确定棋子能够命中任一目标的最早可能时刻。若无法命中任何目标,输出 −1-1。

    输入格式

    第一行:两个整数 nn 和 kk(1≤n, k≤1061 ≤ n,\ k ≤ 10^6),分别表示树的大小和区间数量。

    第二行:n−1n-1 个整数 f2, ..., fnf_2,\ ...,\ f_n(1≤fi<i1 ≤ f_i < i),表示节点 22 到 nn 的父节点编号。

    接下来 kk 行:每行三个整数 ui, li, riu_i,\ l_i,\ r_i(1≤ui≤n1 ≤ u_i ≤ n,1≤li≤ri≤1061 ≤ l_i ≤ r_i ≤ 10^6),描述第 ii 个目标出现的节点及时间区间。

    保证所有区间按顺序给出且互不重叠,即对任意 1≤i<k1 ≤ i < k,满足 ri<li+1r_i < l_{i+1}。

    输出格式

    输出一个整数:命中目标的最早时刻;若不可能,输出 −1-1。

    样例

    8 3
    1 1 1 4 4 6 7
    5 1 1
    8 2 3
    4 5 5
    
    5
    

    样例1解释

    在第一个测试案例中,一种可能的最优策略描述如下:

    时刻 11:棋子从节点 11 移动到节点 44。移动完成后,我们切断节点 66 和 77 之间的边。

    时刻 22 和 33:由于棋子所在的节点 44 与目标节点 88 不连通,棋子保持不动。

    时刻 44:树上没有目标出现,棋子依然保持静止。

    时刻 55:目标恰好出现在棋子所在的节点 44,达成命中条件。

    可以证明,不存在任何策略能在时刻 55 之前实现命中。因此,该案例的答案为 55。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 命中目标