Description：

给一棵有边权的树，每个节点有权值 $v_i$ ，支持往树上添加一个叶子，查询 $dis(x,y)\leqslant v_x+v_y$ 的对数。

强制在线。

$1\leqslant n\leqslant 10^5$

Solution：

树上问题也就几种处理方法，树链剖分，树形 $DP$ ，树上合并，树分治，这个题显然要用点分治。

首先设 $x$ 和 $y$ 到分治重心的距离分别为 $d_x,d_y$ ，那么满足 $d_x+d_y\leqslant v_x+v_y$ ，移一下项就是 $d_x-v_x\leqslant v_y-d_y$ ，那么我们在插入 $y$ 的时候只要统计 $y$ 和其他点产生的贡献，那么就可以在点分树上暴力跳父亲，然后每个点维护一棵平衡树，在平衡树里查一下符合上面那个式子的点的个数，这样显然是会算重多的，所以还要像动态点分治那样维护一个 $tofa$ ，这个也是一棵平衡树，把本来就来自这个点的贡献减掉，这样我们就解决了询问的问题。

但是还有修改呢，既然强制在线也就是说我们必须按照他的要求一步一步把整棵树建出来，但是这样不能保证分治中心始终是树的重心，也就不能保证点分治每次暴力跳父亲的复杂度是对的，也不能保证每个位置的值只会出现在 $\log$ 个平衡树中而不会 $MLE$ ，那么我们就必须动态调整分治中心，具体做法是像替罪羊树那样，记一个 $\alpha$ 表示平衡因子，一般设在 $0.75\sim0.8$ ，然后如果 $\max siz_{son}\geqslant siz_k\times \alpha$ ，也就是说有一个儿子太大了，那就清空这个子树的点分树，然后对这个子树做一次静态的点分治，把点分树重新构建出来就可以了。

题解里巧妙运用了 $vector$ 的 $resize$ 来保证保留了祖先的信息，妙啊。

注意在重构某棵子树的时候他的前一些祖先是没有被修改的，他们的平衡树中还存着这个点的值，但是不影响，只是注意不要再重复插入即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c)){res = (res << 1) + (res << 3) + c - '0';c = getchar();}

	return res * f;

}

int mrandseed = 19260817;

int mrand(){mrandseed = 1ll * mrandseed * 1331331 % 1000000007;return mrandseed;}

#define MAXN 100010

int n;

int f[MAXN][18];

int val[MAXN];

typedef long long ll;

ll dep[MAXN];

int depth[MAXN];

#define MAXNODE 8000010

struct node

{

	int lc,rc;

	int cnt,siz,prio;

	ll val;

	node(){lc = rc = 0;}

}t[MAXNODE];

int sum[MAXN],tofa[MAXN];

int ptr = 0;

int del_node[MAXNODE],del_ptr = 0;

#define R register

inline int newnode(){if(del_ptr != 0)return del_node[del_ptr--];else return ++ptr;}

inline void merge(int k){t[k].siz = t[t[k].lc].siz + t[t[k].rc].siz + t[k].cnt;return;}

inline void lturn(int &k){R int p = t[k].rc;t[k].rc = t[p].lc;t[p].lc = k;t[p].siz = t[k].siz;merge(k);k = p;}

inline void rturn(int &k){R int p = t[k].lc;t[k].lc = t[p].rc;t[p].rc = k;t[p].siz = t[k].siz;merge(k);k = p;}

inline void insert(int &k,ll x)

{

	if(k == 0){k = newnode();t[k].val = x;t[k].prio = mrand();t[k].cnt = t[k].siz = 1;return;}

	if(x == t[k].val){++t[k].cnt;++t[k].siz;return;}

	++t[k].siz;

	if(x < t[k].val){insert(t[k].lc,x);if(t[t[k].lc].prio < t[k].prio)rturn(k);}

	else{insert(t[k].rc,x);if(t[t[k].rc].prio < t[k].prio)lturn(k);}

	return;

}

void restore(int &k)

{

	if(k == 0)return;del_node[++del_ptr] = k;

	restore(t[k].lc);restore(t[k].rc);

	memset(&t[k],0,sizeof(node));k = 0;

	return;

}

int query_rank(int k,ll x)

{

	if(k == 0)return 0;

	if(x < t[k].val)return query_rank(t[k].lc,x);

	else return t[t[k].lc].siz + t[k].cnt + query_rank(t[k].rc,x);

}

ll lastans = 0;

#define MOD 1000000000

#define ALPHA 0.8

#define INF 0x3f3f3f3f

struct edge{int to,nxt;ll v;}e[MAXN << 1];

int ecnt = 0,lin[MAXN] = {0};

inline void add(int a,int b,ll c){e[++ecnt] = (edge){b,lin[a],c};lin[a] = ecnt;e[++ecnt] = (edge){a,lin[b],c};lin[b] = ecnt;}

vector<int> anc[MAXN],son[MAXN];

bool tag[MAXN];

int siz[MAXN],d[MAXN],root,s;

inline void build_doubling(int k,int fa){f[k][0] = fa;for(R int i = 1;i <= 17;++i)f[k][i] = f[f[k][i - 1]][i - 1];}

inline int calc_LCA(int a,int b)

{

	if(depth[a] < depth[b])swap(a,b);

	for(R int i = 17;i >= 0;--i)if(depth[f[a][i]] >= depth[b])a = f[a][i];

	if(a == b)return a;

	for(R int i = 17;i >= 0;--i)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];

	return f[a][0];

}

inline ll calc_dis(int a,int b){return dep[a] + dep[b] - 2 * dep[calc_LCA(a,b)];}

int calc_siz(int k,int fa)

{

	R int size = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!tag[e[i].to] || e[i].to == fa)continue;

		size += calc_siz(e[i].to,k);

	}

	return size;

}

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!tag[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

inline ll extend(int k,int fa)

{

	insert(sum[k],-val[k]);

	anc[k] = anc[fa];anc[k].push_back(k);

	son[anc[k][0]].push_back(k);

	if(fa == 0)return 0;

	R ll res = 0;

	for(R int i = 1;i < anc[k].size();++i)

	{

		son[anc[k][i]].push_back(k);

		R ll dist = calc_dis(k,anc[k][i - 1]);

		res += query_rank(sum[anc[k][i - 1]],val[k] - dist) - query_rank(tofa[anc[k][i]],val[k] - dist);

		insert(sum[anc[k][i - 1]],dist - val[k]);insert(tofa[anc[k][i]],dist - val[k]);

	}

	return res;

}

void divide(int k,int fa,int top)

{

	tag[k] = false;

	anc[k] = anc[fa];anc[k].push_back(k);

	for(R int i = anc[k].size() - 1;i != -1 && anc[k][i] != top;--i)

	{

		son[anc[k][i]].push_back(k);

		insert(sum[anc[k][i]],calc_dis(anc[k][i],k) - val[k]);

		if(i != 0)insert(tofa[anc[k][i]],calc_dis(anc[k][i - 1],k) - val[k]);

	}

	for(R int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!tag[e[i].to])continue;

		root = 0;s = calc_siz(e[i].to,0);

		getroot(e[i].to,0);divide(root,k,top);

	}

	return;

}

inline void rebuild(int &k,int fa)

{

	for(R vector<int>::iterator i = son[k].begin();i != son[k].end();++i)

	{

		if(*i == k)continue;

		anc[*i].clear();son[*i].clear();tag[*i] = true;

		restore(sum[*i]);restore(tofa[*i]);

	}

	anc[k].clear();son[k].clear();tag[k] = true;

	restore(sum[k]);restore(tofa[k]);

	root = 0;s = calc_siz(k,0);d[0] = INF;

	getroot(k,0);

	divide(root,fa,fa);

	return;

}

inline void maintain(int k)

{

	for(R int i = 0;i < anc[k].size() - 1;++i)

	{

		if(t[sum[anc[k][i]]].siz <= 10)break;

		if(i + 1 < anc[k].size() && t[sum[anc[k][i]]].siz * ALPHA <= t[sum[anc[k][i + 1]]].siz)rebuild(anc[k][i],(i == 0 ? 0 : anc[k][i - 1]));

	}

	return;

}

int main()

{

	rd();n = rd();

	R ll lastans = 0;

	R int fa;

	R ll c;

	depth[1] = dep[1] = 1;

	for(R int i = 1;i <= n;++i)

	{

		fa = rd() ^ (lastans % MOD);c = rd();val[i] = rd();

		if(fa != 0)

		{

			add(i,fa,c);build_doubling(i,fa);

			dep[i] = dep[fa] + c;depth[i] = depth[fa] + 1;

		}

		lastans += extend(i,fa);

		printf("%lld\n",lastans);

		maintain(i);

	}

	return 0;

}