Solution
动态点分治 \(+\) treap \(+\) 替罪羊树的思想
容易看出，这题是一个动态的点分治。
静态的点分治是将重心作为分治中心，动态的分治，每次重心都会变，所以就不能以重心作为分治中心。
用重心作为分治中心，是因为这样最能省时间，那么是否可以不用重心呢，显然是可以的。
接下来说一说分治中心的问题。
如图，1是一个分治中心，2,3,4是分出来的子树的分治中心。介绍一个概念：点分树，即所有分治中心形成的树结构。在这张图中，2,3,4在点分树中的父亲为1。
每个分治中心都会计算出一个答案进行累加。如果2的答案作了修改，说明以2为分治中心的子树出现变动，那么3,4的答案不用修改，而1的答案必定修改。
如果1是2,3,4在原树的父亲，同理，2,3,4互不关联，它们都和1有关联。
新插入一个叶结点，它在点分树中也可以作为叶子结点，而它在原树的父亲，也可以作为它在点分树上的父亲。
因此，可以考虑把原树作为点分树。即：把根结点当作整棵树的分治中心，将根结点的子结点当作子树的分治中心。这样每次插入结点时，只要在点分树中找到它原树父亲的位置，插入这个结点作为叶子结点即可。
但是，这样会导致点分树过度不平衡，比如说原树是一条链的情况，每次修改祖先结点的答案都会遍历整棵树。
可以利用替罪羊树的思想，当以某个结点为根的子树过度不平衡时将它重建。
因为按重心分治是最省时间的，所以将这棵点分子树中的所有点进行一次静态的点分治，就相当于将这棵点分子树建成了近似的完全二叉树。
分治中心的问题已经解决了，下面说一说怎么计算答案。
设此时分治中心为u，则：
\(dist(i,j)<=r_i+r_j\) 变为 \(dist(j,u)-r_j<=r_i-dist(i,u)\)
因此，可以对每个 \(u\) 维护一个treap，存储所有 \(dist(j,u)-r_j\) 的值，查找 \(r_i-dist(i,u)\) 的排名，就是所有的情况。查找之后，要将 \(dist(i,u)-r_i\) 加入 \(u\) 的treap，作为以后的 \(j\)。
显然有非法的情况，如下图
\(i\)到\(j\) 的最短路径是不会经过 \(u\) 的，但是可能满足 \(dist(j,u)-r_j<=r_i-dist(i,u)\) ，这种情况非法，应该减掉。
所以对每个点再维护一个treap，存储这种非法的情况。
如图所示，\(u\) 是一个分治中心，\(v\) 是子树的分治中心，结点 \(i\)和\(j\) 在以 \(v\) 为分治中心的子树中， \(v\) 的第二个treap存储所有的 \(dist(j,u)-r_j\)，可以查 \(r_i-dist(i,u)\) 的排名，即非法情况的数量。查完之后，要把 \(dist(i,u)-r_i\) 加入 \(v\) 的第二个treap。
总的来说就是，每个点要存储它所有点分树上的祖先(包括它自己)的编号，以及它到祖先的距离。每次添加一个叶子，先连接它的父亲，可以根据它的父亲的信息，得到它的祖先们的信息。先根据上面的分析，在所有祖先结点中查排名，累计答案，再往所有祖先结点和它的treap加入结点。然后，再从深度浅到深遍历所有祖先结点，找到第一个不满足平衡条件的点，将它的子树中的所有点进行一次静态的点分治，相当于重建点分树。
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
inline int read() //读入优化
{
char ch; int res = 0;
while (ch = getchar(), ch < '0' || ch > '9');
res = ch - 48;
while (ch = getchar(), ch >= '0' && ch <= '9')
res = res * 10 + ch - 48;
return res;
}
const double alpha = 0.777666;
const int e = 1e5+5, mod = 1e9, inf = 0x3f3f3f3f, o = 4000006;
int test, n, r[e], fa[e], sze[e], son[e], num, next[e << 1];
int dist[e], head[e], go[e << 1], cost[e << 1];
long long ans = 0;
bool vis[e];
vector<int>anc[e], id[e], sons[e];
inline void add(int x, int y, int v) //建边
{
next[++num] = head[x];
head[x] = num;
go[num] = y;
cost[num] = v;
next[++num] = head[y];
head[y] = num;
go[num] = x;
cost[num] = v;
}
int unused[o], top, pool, rt_self[e], rt_fa[e];
//当 grav 为分治中心时
//rt_self[grav]表示存储 dist(i, grav) - ri 的 treap 的根结点
//设 grav 在点分树上的父亲为 f
//rt_fa[grav] 表示存储 dist(i, f) - ri 的根结点(非法情况)
struct node
{
int lc, rc, val, s, pos;
}a[o];
inline void reset(int &x, int v)
{
a[x].lc = a[x].rc = 0;
a[x].val = v;
a[x].s = 1;
a[x].pos = rand();
}
inline void update(int &x)
{
a[x].s = a[a[x].lc].s + a[a[x].rc].s + 1;
}
inline int new_node()
{
int res;
if (top > 0)
{
res = unused[top]; //将用过的并且删过的点的编号放入 unused
top--; //新建节点的时候可以再使用这些编号，可以省空间
}
else res = ++pool;
return res;
}
inline void del_node(int &u)
{
if (!u) return;
unused[++top] = u;
a[u].val = a[u].s = a[u].pos = 0;
if (a[u].lc) del_node(a[u].lc);
if (a[u].rc) del_node(a[u].rc);
u = 0;
}
inline void zig(int &u)
{
int v = a[u].lc;
a[u].lc = a[v].rc;
a[v].rc = u;
a[v].s = a[u].s;
update(u);
u = v;
}
inline void zag(int &u)
{
int v = a[u].rc;
a[u].rc = a[v].lc;
a[v].lc = u;
a[v].s = a[u].s;
update(u);
u = v;
}
inline void insert(int &u,int v)
{
if (!u)
{
u = new_node();
reset(u, v);
return;
}
a[u].s++;
if (v <= a[u].val)
{
insert(a[u].lc, v);
if (a[a[u].lc].pos < a[u].pos) zig(u);
}
else
{
insert(a[u].rc, v);
if (a[a[u].rc].pos < a[u].pos) zag(u);
}
}
inline int qrank(int u, int v)
{
if (!u) return 0;
if (v < a[u].val) return qrank(a[u].lc, v);
else return a[a[u].lc].s + 1 + qrank(a[u].rc, v);
}
inline int calc_grav(int &st) //求树的重心
{
static int qn, que[e];
que[qn = 1] = st;
fa[st] = 0;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
sze[u] = 1;
son[u] = 0;
for (int j = head[u]; j; j = next[j])
{
int v = go[j];
if(!vis[v] || v == fa[u])continue;
fa[v] = u;
que[++qn] = v;
}
}
for (int i = qn; i >= 2; i--)
{
int u = que[i], v = fa[u];
sze[v] += sze[u];
if (sze[u] > son[v])
son[v] = sze[u];
}
int all = sze[st], grav = 0, min = inf;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
if (all - sze[u] > son[u])
son[u] = all - sze[u];
if (son[u] < min)
{
min = son[u];
grav = u;
}
}
return grav;
}
inline void dac(int &st, int &par) //静态点分治，用于重建
{
static int qn, que[e];
int grav = calc_grav(st);
vis[grav] = false; // vis[] = false 表示当前这个点已经当过分治中心
que[qn = 1] = grav;
fa[grav] = 0;
dist[grav] = 0;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
for (int j = head[u]; j; j = next[j])
{
int v = go[j];
if (!vis[v] || v == fa[u]) continue;
fa[v] = u;
dist[v] = dist[u] + cost[j];
que[++qn] = v;
}
}
for (int i = 1; i <= qn; i++)
{
int u = que[i];
id[u].push_back(grav);
//id[u][i] 表示 u 在点分树的所有祖先中(包括它自己)第 i 老的编号
anc[u].push_back(dist[u]); //anc[u][i] 就是 dist(u, id[u][i])
//id[u][i] 是 id[u][i+1] 点分树中的父亲，anc 同理
sons[grav].push_back(u); //sons[u] 存储在点分树中u的子树的所有节点
insert(rt_self[grav], dist[u] - r[u]); //所有情况
if (par != 0)
insert(rt_fa[grav], anc[u][anc[u].size() - 2] - r[u]); //非法情况
}
for (int i = head[grav]; i; i = next[i])
{
int v = go[i];
if (vis[v]) dac(v, grav);
}
}
inline void rebuild(int &u, int par) //重建点分树的某一子树
{
vector<int>tmpson = sons[u];
//要先把原来的 sons[u] 存了，因为下面 sons[v].clear
int notres = anc[par].size(), len = tmpson.size();
for (int i = 0; i < len; i++) //先把这棵子树部分的信息删了
{
int v = tmpson[i];
vis[v] = true;
sons[v].clear();
anc[v].resize(notres); //仅与子树的根结点的祖先们有关的信息还要留着
id[v].resize(notres);
del_node(rt_self[v]);
del_node(rt_fa[v]);
}
dac(u, par); //再将这棵子树中的所有点进行一次静态的点分治
}
inline void check(int &u)
{
int len = anc[u].size();
for (int i = 0; i < len; i++)
{
insert(rt_self[id[u][i]], anc[u][i] - r[u]);
//所有祖先的 treap (包括它自己的)都要插入新结点
if (i != 0)
insert(rt_fa[id[u][i]], anc[u][i - 1] - r[u]);
}
for (int i = 0; i < len - 1; i++)
{
int sze_fa = a[rt_self[id[u][i]]].s;
int sze_son = a[rt_self[id[u][i + 1]]].s;
if (sze_fa <= 30)break;
if (sze_son > alpha * sze_fa) //过度不平衡，重建
{
rebuild(id[u][i], i == 0 ? 0 : id[u][i - 1]);
break;
}
}
}
inline int calc_ans(int &u, int &v, int &w)
{
int res = 0;
anc[u] = anc[v]; //当前结点的父亲的祖先也是它的祖先
id[u] = id[v]; //存储的信息先由它父亲得来
anc[u].push_back(-w); //和 += w 抵消
id[u].push_back(u);
int len = anc[u].size();
for (int i = 0; i < len; i++)
{
anc[u][i] += w;
sons[id[u][i]].push_back(u);
res += qrank(rt_self[id[u][i]], r[u] - anc[u][i]);
//查询 r[u] - dist(u, id[u][i]) 的排名，即所有的情况
if (i != 0)
res -= qrank(rt_fa[id[u][i]], r[u] - anc[u][i - 1]);
//查询 r[u] - dist(u, id[u][i] 的父亲) 的排名，即非法情况
}
return res;
}
int main()
{
test = read();
n = read();
for (int i = 1; i <= n; i++)
{
int fa_i = read(), c = read();
r[i] = read();
fa_i ^= (ans % mod);
if(i == 1)
{
anc[i].push_back(0);
id[i].push_back(i);
sons[i].push_back(i);
insert(rt_self[i], -r[i]); //第一个结点 dist 为 0
puts("0");
continue;
}
add(fa_i, i, c);
ans += calc_ans(i, fa_i, c); //累加包含当前结点且满足条件的点对的个数
check(i); //往所有祖先结点和它的 treap 加入结点
//并检查是否存在过度不平衡现象
printf("%lld\n", ans);
}
return 0;
}