P3920 [WC2014]紫荆花之恋

    • 844通过
    • 2.4K提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签 分治 平衡树 点分治 WC/CTSC/集训队 2014 O2优化 新云端
  • 难度 NOI/NOI+/CTSC
  • 时空限制 12000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    警告,滥用本题者将被封号。

    题目描述

    强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

    仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 $i$ 都有一个感受能力值 $r_i$ ,小精灵 $i,j$ 成为朋友当且仅当在树上 $i$ 和 $j$ 的距离 $dist(i,j)<=ri+rj$ ,其中 $dist(i,j)$ 表示在这个树上从 $i$ 到 $j$ 的唯一路径上所有边的边权和。

    强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。

    我们假定这个树一开始为空,节点按照加入的顺序从 1 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。

    输入输出格式

    输入格式:

    第一行包含一个整数,表示测试点编号。

    第二行包含一个正整数 $n$ ,表示总共要加入的节点数。

    我们令加入节点前的总共朋友对数是 $last\_ans$ ,在一开始时它的值为 0。

    接下来 $n$ 行中第 $i$ 行有三个非负整数 $ai,ci,ri$ ,表示结点 i 的父节点的编号为 $ai \; xor \; (last\_ans \; mod \; 10^9)$ (其中 $xor$ 表示异或, $mod$ 表示取余,数据保证这样操作后得到的结果介于 1 到 $i−1$ 之间),与父结点之间的边权为 $c_i$ ,节点 $i$ 上小精灵的感受能力值为 $ri$ 。

    注意 $a1=c1=0$ ,表示 1 号节点是根结点,对于 $i>1$ ,父节点的编号至少为 1。

    输出格式:

    包含 $n$ 行,每行输出 1 个整数,表示加入第 $i$ 个点之后,树上有几对friends。

    输入输出样例

    输入样例#1: 复制
    0
    5
    0 0 6
    1 2 4
    0 9 4
    0 5 5
    0 2 4
    
    输出样例#1: 复制
    0
    1
    2
    4
    7
    

    说明

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。