思路
点分树 + 根号重构 + *高速平衡树。
点分树的两种常见用法无非是 直接做和路径有关的暴力 还有 处理这种有关单点和整树的问题，后者的另一个经典题目是 P3241 [HNOI2015]开店。
回到这个题目，处理路径考虑先上点分治，暂时不考虑强制在线的限制。
因为每次加上一个新点，所以可以考虑在加点的过程中动态维护答案，于是问题变成维护每次加点之后答案的增量。
也就是说对于新加入的点 \(u\)，每次询问原树中满足 \(\operatorname{dist}(u, v) \leq r_u + r_v\) 的点 \(v\) 的个数。
等式变形成 \(\operatorname{dist}(u, v) - r_u \leq r_v\)，似乎不太好在点分的过程中处理 \(\operatorname{dist}(u, v)\).
一般情况下考虑的是把 \(u, v\) 之间的路径拆成 \(\{u, \cdots, \operatorname{lca}(u, v)\}\) 和 \(\{\operatorname{lca}(u, v), \cdots, v\}\) 两部分，但是 \(\operatorname{lca}\) 在点分的过程中难以钦定。
又因为实际上可以从路径上的任意一点断开，所以可以联想到点分树的一个很好的性质：点分树上两点的 \(\operatorname{lca}\) 在原树中一定在这两点的路径上，并且点分树的树高是 \(O(\log)\) 的。
这意味着我们可以从点 \(u\) 向上枚举 \(\operatorname{lca}\) 然后处理点 \(v\) 的个数。
先考虑静态询问怎么做。假设当前枚举到 \(u\) 的祖先 \(x\)。原式可以化成 \(\operatorname{dist}(u, x) + \operatorname{dist}(x, v) \leq r_u + r_v\)，调整成关于 \(v\) 的限制就是 \(\operatorname{dist}(u, x) - r_u \leq r_v - \operatorname{dist}(x, v)\).
注意到等式的左边在枚举祖先的时候可以视作一个定值，于是我们只需要知道 \(x\) 的子树中满足 \(r_v - \operatorname{dist}(x, v)\) 大于等于某一个定值的点的个数就可以了。
常规的树论做法都不太可行，考虑一些和点分树性质有关的暴力。
因为点分树的树高是 \(O(\log)\) 级别的，所以对于每个结点大力存储下它子树中信息的总复杂度是 \(O(n \log n)\).
这意味着我们可以预先将 \(x\) 子树中所有的结点的 \(r_v - \operatorname{dist}(x, v)\) 用某种神秘的数据结构维护一下，之后询问就是在上面查询的事情。
因为动态加点没法离散化，所以选择用平衡树实现。
注意到向上枚举的过程中会算重子结点的子树，所以还需要维护 \(r_v - \operatorname{dist}(fa_x, v)\) 用来容斥。
然后再考虑如何维护动态插入结点。
不考虑点分树的性质，那么直接将新点接在原树父亲下面就行，可以看作是钦定在父亲处点分一次，然后在这个孤点在进行一次点分。现在的问题是这样做不能保证复杂度。
于是考虑类似替罪羊树的思路，当某棵子树失衡的时候就暴力调整。钦定一个比例系数 \(\alpha\)，如果插入点 \(u\) 后其祖先 \(x\) 满足 \(\operatorname{size}(x) \geq \alpha \cdot \operatorname{size}(fa_x)\)，就直接暴力重建 \(x\) 的子树。
具体的复杂度就是调参，\(\alpha\) 在 \(0.8\) 左右的时候点分树的树高大概还是 \(O(\log)\)（但我不会证，有懂的老哥麻烦教一下
如果要再偷懒的话可以不写平衡树，用 vector + 根号重构平替。具体考虑维护两个 vector，一个当作缓存池存当前加入的数据，另一个用来存溢出的数据。当缓存池超过根号大小的时候就暴力归并。
查询直接在 vector 里二分。
这个在很多阴间根号题都有应用，\(O(n \sqrt{n})\) 应该比较快。
复杂度懒得算了，反正常数已经挺离谱了。
代码
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define il inline
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxe = maxn << 1;
const int lg_sz = 17;
const int lim = 350;
const int inf = 0x3f3f3f3f;
const double alpha = 0.95;
struct node
{
int to, nxt;
} edge[maxe];
int n, ecnt;
int r[maxn], head[maxn], sz[maxn];
bool vis[maxn];
ll last_ans;
namespace IO
{
//by cyffff
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 26) + 1];
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define reg register
il int read()
{
reg char ch = gh();
reg int x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
return t ? -x : x;
}
il void putc(char ch) { out[len++] = ch; }
template<class T>
il void write(T x)
{
if (x < 0) putc('-'), x = -x;
if (x > 9) write(x / 10);
out[len++] = x % 10 + 48;
}
il void flush()
{
fwrite(out, 1, len, stdout);
len = 0;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;
il void add_edge(int u, int v)
{
ecnt++;
edge[ecnt].to = v, edge[ecnt].nxt = head[u];
head[u] = ecnt;
}
il pair<int, int> get_rt(int u, int f, int tot)
{
sz[u] = 1;
int res = 0;
pair<int, int> ans = make_pair(inf, 0);
for (int i = head[u], v; i; i = edge[i].nxt)
{
v = edge[i].to;
if ((!vis[v]) && (v != f))
{
ans = min(ans, get_rt(v, u, tot));
sz[u] += sz[v], res = max(res, sz[v]);
}
}
ans = min(ans, make_pair(max(res, tot - sz[u]), u));
return ans;
}
namespace tree
{
int f[lg_sz][maxn], dep[maxn], dis[maxn];
il void insert(int u, int fa, int w)
{
f[0][u] = fa, dep[u] = dep[fa] + 1, dis[u] = dis[fa] + w;
for (int i = 1; i < lg_sz; i++) f[i][u] = f[i - 1][f[i - 1][u]];
}
il int lca(int u, int v)
{
if (dep[u] < dep[v]) swap(u, v);
for (int i = lg_sz - 1; ~i; i--)
if (dep[f[i][u]] >= dep[v]) u = f[i][u];
if (u == v) return u;
for (int i = lg_sz - 1; ~i; i--)
if (f[i][u] != f[i][v]) u = f[i][u], v = f[i][v];
return f[0][u];
}
il int calc_dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; }
}
struct item
{
vector<int> lrg, sml;
il void insert(int w)
{
sml.insert(lower_bound(sml.begin(), sml.end(), w), w);
if (sml.size() >= lim)
{
vector<int> res, emp;
int i = 0, j = 0;
for ( ; (i < lrg.size()) && (j < sml.size()); )
if (lrg[i] < sml[j]) res.push_back(lrg[i++]);
else res.push_back(sml[j++]);
while (i < lrg.size()) res.push_back(lrg[i++]);
while (j < sml.size()) res.push_back(sml[j++]);
swap(lrg, res), swap(sml, emp);
}
}
il int calc_rk(int w) { return (upper_bound(lrg.begin(), lrg.end(), w) - lrg.begin()) + (upper_bound(sml.begin(), sml.end(), w) - sml.begin()) - 2; }
il void clear() { lrg.clear(), sml.clear(); }
} subt[maxn << 1], tof[maxn << 1];
namespace divide
{
int fa[maxn], dep[maxn], siz[maxn];
il int query(int u, int w)
{
int res = 0;
for (int i = u, j; fa[i]; i = j)
{
j = fa[i];
int x = w - tree::calc_dis(u, j);
res += subt[j].calc_rk(x) - tof[i].calc_rk(x);
// printf("debug %d -> %d, %d\n", i, u, fa[i]);
}
return res;
}
il void insert(int u, int w, int anc)
{
subt[u].insert(-w);
// puts("subt insert done");
for (int i = u, j; i != anc; i = j)
{
j = fa[i];
// printf("for %d %d\n", i, fa[i]);
int x = tree::calc_dis(u, j) - w;
if (j != anc) subt[j].insert(x);
tof[i].insert(x);
}
// puts("insert ok");
}
il void clear(int u, int fa, int anc_dep)
{
vis[u] = false;
for (int i = head[u], v; i; i = edge[i].nxt)
{
v = edge[i].to;
if ((v != fa) && (dep[v] > anc_dep)) clear(v, u, anc_dep);
}
}
il int build(int u, int tot_sz, int f, int anc)
{
// puts("begin build");
int rt = get_rt(u, 0, tot_sz).second, bas = sz[u];
subt[rt].clear(), tof[rt].clear();
// if (fa[rt] == f) printf("cir %d\n", rt);
fa[rt] = f, siz[rt] = 1, vis[rt] = true, dep[rt] = dep[f] + 1;
// puts("begin insert");
// if (fa[rt] == f) printf("debg %d\n", u);
insert(rt, r[rt], anc);
// puts("insert done");
for (int i = head[rt], v; i; i = edge[i].nxt)
{
v = edge[i].to;
if (!vis[v]) siz[rt] += build(v, bas, rt, anc);
}
// puts("build done");
return siz[rt];
}
il void rebuild(int u) { clear(u, 0, dep[u]), build(u, siz[u], fa[u], fa[u]); }
il void insert(int u, int w)
{
subt[u].insert(-w), siz[u]++;
int nd = 0;
for (int i = u, j; fa[i]; i = j)
{
j = fa[i];
// printf("cur %d : %d\n", i, fa[i]);
// if ((i == 86) && (fa[i] == 85)) printf("debug %d %d\n", u, w);
int x = tree::calc_dis(u, j) - w;
siz[j]++, subt[j].insert(x), tof[i].insert(x);
if (siz[i] > siz[j] * alpha) nd = j;
// if (last_ans == 5433) printf("doadmoadnd %d\n", j);
// if (last_ans == 5433 && j == 85) printf("%d %d %d %d\n", i, j, siz[i], siz[j]);
}
// if (last_ans == 5433) printf("debug nd = %d, %d\n", nd, siz[85]);
if (nd) rebuild(nd);
// puts("solve done");
}
}
int main()
{
// freopen("P3920_3.in", "r", stdin);
// freopen("P3920_3.res", "w", stdout);
read(), n = read();
for (int i = 1; i <= n; i++)
{
vis[i] = true;
int fa = read() ^ last_ans % (int)1e9, c = read();
// printf("read fa = %d\n", fa);
r[i] = read();
tree::insert(i, fa, c);
if (i > 1) add_edge(fa, i), add_edge(i, fa);
divide::fa[i] = fa, divide::dep[i] = divide::dep[fa] + 1;
write(last_ans += divide::query(i, r[i])), putc('\n');
divide::insert(i, r[i]);
// printf("done %lld\n", last_ans);
}
flush();
return 0;
}