如果这棵树不变的话，就是一个裸的点分树套平衡树，式子也很好推$di+dj<=ri+rj$，$ri-di>=dj-rj$ 平衡树维护$dj-rj$，然后查$ri-di$的$rank$即可。
但是点分树如果极度不平衡也就没有什么意义了。所以利用替罪羊树的思想，当某个子树极度不平衡时，就重新找重心，重建点分树。时间复杂度$O(nlg^2n)$，无旋Treap被卡，有旋Treap常数十分优秀。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define L 1<<20
char _buf[L],*SS,*TT,c;
const int BufS=,md=;
char buf[BufS],*inss=buf,*outs=buf,num[];
inline void pl(register long long a){
if(!a){*outs++='',*outs++='\n';return;}
register int tp=;while(a)num[tp++]=a%,a/=;
while(tp--)*outs++=num[tp]+'';*outs++='\n';
}
#define gc() (SS==TT&&(TT=(SS=_buf)+fread(_buf,1,L,stdin),SS==TT)?0:*SS++)
int get()
{
for(c=gc();c<''||c>'';c=gc());
int x=c^'';
for(c=gc();c>=''&&c<='';c=gc())x=x*+(c^'');
return x;
}
#define N 100050
int n;
long long ans;
namespace Treap{
#define tp pair<Node*,Node*>
struct Node{
Node *ch[];
int key,val,size;
void pushup(){
size=ch[]->size+ch[]->size+;
}
Node(int k);
}*null=new Node(),*root[N],*root1[N];
Node :: Node(int k){
key=k;val=rand();size=;
ch[]=ch[]=null;
}
void init(){
null->ch[]=null->ch[]=null;
null->key=null->val=null->size=;
for(int i=;i<=::n;i++)root[i]=root1[i]=null;
}
int getrank(Node *now,int x){
int ans=;
while(now!=null){
if(now->key<x)ans+=now->ch[]->size+,now=now->ch[];
else now=now->ch[];
}
return ans;
}
void rotate(Node *&x,int d){
Node *y=x->ch[d];
x->ch[d]=y->ch[d^];
y->ch[d^]=x;
x->pushup();y->pushup();
x=y;
}
void insert(Node *&rt,int x){
if(rt==null)rt=new Node(x);
else{
int d=x>rt->key;
insert(rt->ch[d],x);
if(rt->ch[d]->val<rt->val)rotate(rt,d);
}
rt->pushup();
}
void dfs(Node *rt){
if(rt==null)return;
dfs(rt->ch[]);
dfs(rt->ch[]);
delete rt;
}
}
int head[N],e=;
struct edge{
int v,next;
}ed[N<<];
void add(int u,int v){
ed[e].v=v;ed[e].next=head[u];
head[u]=e++;
}
int dep[N],val[N],fa[N][],r[N],w[N];
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=;~i;i--)
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=;~i;i--)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][];
}
int dis(int x,int y){
return val[x]+val[y]-*val[lca(x,y)];
}
int size[N],maxn[N],root,sum;
bool vis[N];
int f[N],S[N];
void getroot(int x,int fa){
size[x]=;maxn[x]=;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==fa||!vis[v])continue;
getroot(v,x);
size[x]+=size[v];
maxn[x]=max(maxn[x],size[v]);
}
maxn[x]=max(maxn[x],sum-size[x]);
if(maxn[x]<maxn[root])root=x;
}
void init(int x,int fa){
f[x]=fa;vis[x]=;
int all=sum;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(!vis[v])continue;
sum=size[v]<size[x]?size[v]:all-size[x];
root=;
getroot(v,);
init(root,x);
}
}
int T,tim[N];
void dfs1(int x,int fa,int s){
vis[x]=;sum++;S[x]=;tim[x]=T;
dfs(Treap::root[x]);Treap::root[x]=Treap::null;
dfs(Treap::root1[x]);Treap::root1[x]=Treap::null;
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==fa||S[v]>s)continue;
dfs1(v,x,s);
}
}
void dfs2(int x,int fa,int en){
int now=x;
while(now!=en){
S[now]++;
Treap::insert(Treap::root[now],dis(x,now)-r[x]);
if(f[now])Treap::insert(Treap::root1[now],dis(x,f[now])-r[x]);
now=f[now];
}
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==fa||tim[v]!=T)continue;
dfs2(v,x,en);
}
}
void rebuild(int x){
int fa=f[x];T++;sum=;
dfs1(x,,S[x]);root=;
getroot(x,);
init(root,fa);
dfs2(x,,fa);
}
int query(int x){
int now=x;
int cnt=getrank(Treap::root[now],r[x]+);
while(f[now]){
cnt+=Treap::getrank(Treap::root[f[now]],r[x]-dis(x,f[now])+)
-Treap::getrank(Treap::root1[now],r[x]-dis(x,f[now])+);
now=f[now];
}
return cnt-;
}
void insert(int x){
if(x>)add(x,f[x]),add(f[x],x);
fa[x][]=f[x];
dep[x]=dep[fa[x][]]+;
val[x]=val[f[x]]+w[x];
for(int i=;(<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-]][i-];
S[x]++;
int now=x,ret=;
while(f[now]){
Treap::insert(Treap::root[now],dis(x,now)-r[x]);
Treap::insert(Treap::root1[now],dis(x,f[now])-r[x]);
S[f[now]]++;
if(S[now]>S[f[now]]*0.88)ret=f[now];
now=f[now];
}Treap::insert(Treap::root[now],dis(x,now)-r[x]);
if(ret)rebuild(ret);
ans+=query(x);
}
int main(){
n=get();n=get();maxn[]=N;
Treap::init();
for(int i=;i<=n;i++){
f[i]=get();w[i]=get();r[i]=get();
f[i]=f[i]^(ans%);
insert(i);
printf("%lld\n",ans);
}
return ;
}