NKOJ 2703-WC 2014 紫荆花之恋-点分治-平衡树-替罪羊

P2703【WC2014】紫荆花之恋（强数据版）

问题描述

强强与萌萌是亲密无间的好友。某日，他们在街头漫步时，偶然发现前方有一棵紫荆树。此时正值紫荆花凋零的时节，无数花瓣正以肉眼可见的速度从树上脱落。
若仔细观察，这棵大树实际上是一棵带权树。在每个时间点，都会新增一个叶子节点。每个节点上都栖息着一只可爱的小精灵，新生成的节点也会同步出现一只新的小精灵。小精灵虽然可爱但十分脆弱，每个小精灵i都有一个特定的感受能力ri。当且仅当i和j在树上的距离dist(i,j)不超过ri+rj时，小精灵i与j才能成为朋友，其中dist(i,j)表示在这棵树中i和j之间唯一路径上所有边的边权总和。
强强与萌萌对每次新增一个叶子节点后整棵树中朋友对的数量感到好奇。
假设初始时这棵树为空，并且节点按照加入顺序从1开始编号。由于强强非常好奇，你必须在每次新增节点后立即给出当前的朋友对总数，不得有任何延迟。

输入格式

输入文件共包含n+2行内容。
首行是一个正整数T，代表测试点编号。
第二行是一个正整数n，表示总共需要添加的节点数量。
我们用last_ans表示之前累计的朋友对数，在初始状态下last_ans=0。
接下来的n行中第i行包含三个数值ai,ci,ri：表示第