传送门

暴力思路就是每次点分治计算答案

点分治之后，条件可以变成 \(dis_i-r_i\le r_j-dis_j\)

每次只要查找 \(r_j-dis_j\) 的排名然后插入 \(dis_j-r_j\)，随便拿个平衡树维护即可

考虑如果带修改，就是动态点分治，每个点维护两个平衡树，一个表示自己的贡献，一个表示上一层重心要减去的在同一棵子树的贡献

每次加入一个点就直接在父亲下面，暴力向上更新每一个重心的两个平衡树，顺便查询答案

求距离什么的直接暴力维护倍增数组就行了

现在的问题就是可能暴力向上更新的时候链长过大

这个时候运用替罪羊树的思想，维护一个 \(size\)，不平衡就暴力重构这个点分树子树的所有信息即可

把1e9看成是1e9+7调了一年

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace IO {

	const int maxn(1 << 21 | 1);

	char ibuf[maxn], obuf[maxn], *iS, *iT, *oS = obuf, *oT = obuf + maxn - 1, c, st[66];

	int tp, f;

	inline char Getc() {

		return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++;

	}

	template <class Int> inline void In(Int &x) {

		for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;

		for (x = 0; c >= '0' && c <= '9'; c = Getc()) x = (x << 1) + (x << 3) + (c ^ 48);

		x *= f;

	}

	inline void Flush() {

		fwrite(obuf, 1, oS - obuf, stdout);

		oS = obuf;

	}

	inline void Putc(char c) {

		*oS++ = c;

		if (oS == oT) Flush();

	}

	template <class Int> void Out(Int x) {

		if (!x) Putc('0');

		if (x < 0) Putc('-'), x = -x;

		while (x) st[++tp] = x % 10 + '0', x /= 10;

		while (tp) Putc(st[tp--]);

	}

}

using IO :: In;

using IO :: Out;

using IO :: Putc;

using IO :: Flush;

const int maxn(2e5 + 5);

const int maxm(8e6 + 5);

const int mod(1e9);

const double alpha(0.75);

namespace BT {

	int ls[maxm], rs[maxm], size[maxm], val[maxm], trash[maxm], top, tot, que[maxm], len, rt[maxn];

	inline int NewNode(int v) {

		int o = top ? trash[top--] : ++tot;

		assert(tot < maxm);

		ls[o] = rs[o] = 0, size[o] = 1, val[o] = v;

		return o;

	}

	void Recycle(int x) {

		if (!x) return;

		trash[++top] = x, Recycle(ls[x]), Recycle(rs[x]);

	}

	inline void Clear(int x) {

		Recycle(rt[x]), rt[x] = 0;

	}

	void Rebuild(int x) {

		if (!x) return;

		Rebuild(ls[x]), que[++len] = x, Rebuild(rs[x]);

	}

	int Build(int l, int r) {

		if (l > r) return 0;

		int mid = (l + r) >> 1, o = que[mid];

		ls[o] = Build(l, mid - 1), rs[o] = Build(mid + 1, r);

		size[o] = size[ls[o]] + size[rs[o]] + 1;

		return o;

	}

	void Insert(int &x, int v) {

		if (!x) x = NewNode(v);

		else {

			if (alpha * size[x] < max(size[ls[x]], size[rs[x]])) len = 0, Rebuild(x), x = Build(1, len);

			v <= val[x] ? Insert(ls[x], v) : Insert(rs[x], v);

			size[x] = size[ls[x]] + size[rs[x]] + 1;

		}

	}

	int Kth(int x, int v) {

		if (!x) return 0;

		if (v >= val[x]) return Kth(rs[x], v) + size[ls[x]] + 1;

		return Kth(ls[x], v);

	}

}

int n, r[maxn], first[maxn], cnt, dis[maxn], fa[maxn][18], deep[maxn], frt[maxn], vis[maxn], idx;

int sz[maxn], nsz, mx[maxn], rt, mark[maxn], size[maxn];

struct Edge {

	int to, next, w;

} edge[maxn];

inline void Add(int u, int v, int w) {

	edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;

	edge[cnt] = (Edge){u, first[v], w}, first[v] = cnt++;

}

inline int LCA(int x, int y) {

	int i;

	if (deep[x] < deep[y]) swap(x, y);

	for (i = 17; ~i; --i)

		if (deep[fa[x][i]] >= deep[y]) x = fa[x][i];

	if (x == y) return x;

	for (i = 17; ~i; --i)

		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];

	return fa[x][0];

}

inline int Dis(int x, int y) {

	return dis[x] + dis[y] - (dis[LCA(x, y)] << 1);

}

void Clear(int u, int ff) {

	int e, v;

	mark[u] = 0, BT :: Clear(u), BT :: Clear(u + n);

	for (e = first[u]; ~e; e = edge[e].next)

		if (((v = edge[e].to) ^ ff) && (vis[v] ^ idx)) Clear(v, u);

}

void Getroot(int u, int ff) {

	int e, v;

	sz[u] = 1, mx[u] = 0;

	for (e = first[u]; ~e; e = edge[e].next)

		if (((v = edge[e].to) ^ ff) && (vis[v] ^ idx)) {

			Getroot(v, u);

			sz[u] += sz[v], mx[u] = max(mx[u], sz[v]);

		}

	mx[u] = max(mx[u], nsz - sz[u]);

	if (!rt || mx[u] < mx[rt]) rt = u;

}

void Getdis(int u, int ff, int nrt, int d) {

	int e, v;

	BT :: Insert(BT :: rt[nrt], d - r[u]);

	if (frt[nrt]) BT :: Insert(BT :: rt[nrt + n], Dis(frt[nrt], u) - r[u]);

	for (e = first[u]; ~e; e = edge[e].next)

		if (((v = edge[e].to) ^ ff) && (vis[v] ^ idx)) Getdis(v, u, nrt, d + edge[e].w);

}

void Build(int u) {

	int e, v;

	vis[u] = idx, Getdis(u, 0, u, 0);

	for (e = first[u]; ~e; e = edge[e].next)

		if (vis[v = edge[e].to] ^ idx) {

			rt = 0, nsz = sz[v], Getroot(v, u);

			frt[rt] = u, size[rt] = sz[v], Build(rt);

		}

}

inline void Rebuild(int u) {

	int x;

	for (++idx, x = frt[u]; x; x = frt[x]) vis[x] = idx;

	Clear(u, 0), rt = 0, nsz = size[u], Getroot(u, 0);

	frt[rt] = frt[u], size[rt] = sz[u], Build(rt);

}

void Update(int u, int v, ll &ans) {

	if (!frt[u]) {

		if (mark[u]) Rebuild(u);

		return;

	}

	int d = Dis(frt[u], v);

	ans += BT :: Kth(BT :: rt[frt[u]], r[v] - d);

	BT :: Insert(BT :: rt[frt[u]], d - r[v]);

	ans -= BT :: Kth(BT :: rt[u + n], r[v] - d);

	BT :: Insert(BT :: rt[u + n], d - r[v]);

	++size[frt[u]];

	if (frt[u] && alpha * size[frt[u]] < size[u]) mark[frt[u]] = 1;

	Update(frt[u], v, ans);

	if (mark[u]) Rebuild(u);

}

int main() {

	int i, c, j;

	ll ans = 0;

	memset(first, -1, sizeof(first)), deep[1] = 1;

	In(c), In(n);

	for (i = 1; i <= n; ++i) {

		In(fa[i][0]), In(c), In(r[i]);

		fa[i][0] ^= ans % mod;

		if (fa[i][0]) {

			Add(fa[i][0], i, c);

			for (j = 1; j <= 17; ++j) fa[i][j] = fa[fa[i][j - 1]][j - 1];

		}

		deep[i] = deep[fa[i][0]] + 1, dis[i] = dis[fa[i][0]] + c;

		frt[i] = fa[i][0], size[i] = 1;

		BT :: Insert(BT :: rt[i], -r[i]), Update(i, i, ans);

		Out(ans), Putc('\n');

	}

	return Flush(), 0;

}