https://www.lydsy.com/JudgeOnline/problem.php?id=3435
https://www.luogu.org/problemnew/show/P3920
强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i 都有一个感受能力值Ri ，小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离 dist(i,j) ≤ Ri + R! ，其中 dist(i, j)表示在这个树上从 i 到 j 的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇， 你必须在他每次出现新节点后马上给出总共的朋友对数，不能拖延哦。
对着题解的指针魔改了一个在洛谷开O2可过，其他网站可过的数组版。
题解请见：https://www.luogu.org/blog/user15268/solution-p3920
其实理解起来还是很好理解的，关键就在于你的卡常姿势以及代码能力的问题了。
（然而考场谁写谁跪的谁敢写这东西……）
简单叙述题解：
树不会动的时候显然点分治，把条件拆开即可用平衡树维护做（比较基础的点分治，具体做法看参考）。
树会动思考点分治并非一定要重心，只有当差的太离谱时为了效率将点重新变为重心就行。
这就是替罪羊树的思想了：暴力维护，失衡时暴力重建。我们把这样的点所构成的结构叫做点分树。
那最开始的点分树就随便搞，失衡了再静态维护一下即可。
总代码压行后198行……应该不影响阅读，因为linux的问题缩进被吃了一些请见谅。
#include<cmath>
#include<stack>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int N=1e5+;
const int mod=1e9;
const dl alpha=0.812345;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
inline void put(ll x){
if(x>)put(x/);
putchar(x%+);
}
struct node{
int to,nxt,w;
}e[N*];
int cnt,head[N],r[N],fa[N],size[N],son[N],dis[N],n,q[N];
vector<int>anc[N],id[N],sons[N];
bool vis[N];
ll ans;
int t[*N][],s[*N],p[*N],w[*N];
int sz,rt[*N];
stack<int>bin;
inline void add(int u,int v,int w){
e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}
inline int rand(){
static int seed=;
return seed=(ll)seed*%;
}
inline int f(int x){return x+n;}
inline int getnod(){
if(!bin.empty()){
int u=bin.top();bin.pop();
return u;
}
return ++sz;
}
inline void upt(int k){
s[k]=s[t[k][]]+s[t[k][]]+;
}
inline void zig(int &k){
int y=t[k][];t[k][]=t[y][];t[y][]=k;
s[y]=s[k];upt(k);
k=y;
}
inline void zag(int &k){
int y=t[k][];t[k][]=t[y][];t[y][]=k;
s[y]=s[k];upt(k);
k=y;
}
inline void del(int &k){
if(!k)return;
bin.push(k);
if(t[k][])del(t[k][]);
if(t[k][])del(t[k][]);
k=;
}
inline void insert(int &k,int val){
if(!k){
k=getnod();w[k]=val;p[k]=rand();
s[k]=;t[k][]=t[k][]=;
return;
}
else ++s[k];
if(val<=w[k]){
insert(t[k][],val);
if(p[t[k][]]<p[k])zig(k);
}else{
insert(t[k][],val);
if(p[t[k][]]<p[k])zag(k);
}
}
inline int find(int x,int val){
int res=;
while(x){
if(val<w[x])x=t[x][];
else res+=s[t[x][]]+,x=t[x][];
}
return res;
}
int calcg(int st){
int R=,g,maxn=n;
q[++R]=st;fa[st]=;
for(int L=;L<=R;++L){
int u=q[L];
size[u]=;son[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]||v==fa[u])continue;
fa[v]=u;q[++R]=v;
}
}
for(int L=R;L>=;--L){
int u=q[L],v=fa[u];
if(R-size[u]>son[u])son[u]=R-size[u];
if(son[u]<maxn)g=u,maxn=son[u];
if(!v)break;
size[v]+=size[u];
if(size[u]>son[v])son[v]=size[u];
}
return g;
}
inline void dac(int st,int par){
int R=,g=calcg(st);vis[g]=;
q[++R]=g;fa[g]=;dis[g]=;
for(int L=;L<=R;++L){
int u=q[L];
for(int j=head[u];j;j=e[j].nxt){
int v=e[j].to;
if(!vis[v]||v==fa[u])continue;
fa[v]=u;dis[v]=dis[u]+e[j].w;
q[++R]=v;
}
}
for(int L=;L<=R;++L){
int u=q[L];
id[u].push_back(g);
anc[u].push_back(dis[u]);
sons[g].push_back(u);
insert(rt[g],dis[u]-r[u]);
if(par)insert(rt[f(g)],anc[u][anc[u].size()-]-r[u]);
}
for(int i=head[g];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v])dac(v,g);
}
}
vector<int>tmp;
inline void rebuild(int u,int par){
tmp=sons[u];
int len=anc[par].size();
for(int i=;i<tmp.size();++i){
int v=tmp[i];vis[v]=;
sons[v].clear();
anc[v].resize(len);
id[v].resize(len);
del(rt[v]);del(rt[f(v)]);
}
dac(u,par);
}
inline void check(int u){
for(int i=;i<id[u].size();++i){
insert(rt[id[u][i]],anc[u][i]-r[u]);
if(i)insert(rt[f(id[u][i])],anc[u][i-]-r[u]);
}
for(int i=;i<id[u].size()-;++i){
int sz_f=s[rt[id[u][i]]];
int sz_s=s[rt[id[u][i+]]];
if(sz_f<=)return;
if(sz_s>alpha*sz_f){
rebuild(id[u][i],(!i)?:id[u][i-]);
return;
}
}
}
inline int solve(int u,int v,int w){
int res=;
anc[u]=anc[v];id[u]=id[v];
anc[u].push_back(-w);id[u].push_back(u);
for(int i=;i<anc[u].size();++i){
anc[u][i]+=w;
sons[id[u][i]].push_back(u);
res+=find(rt[id[u][i]],r[u]-anc[u][i]);
if(i)res-=find(rt[f(id[u][i])],r[u]-anc[u][i-]);
}
return res;
}
int main(){
read();n=read();
for(int i=;i<=n;++i){
int u=read()^(ans%mod),w=read();r[i]=read();
if(i==){
anc[i].push_back();
id[i].push_back(i);
sons[i].push_back(i);
insert(rt[i],-r[i]);
puts("");
continue;
}
add(u,i,w);add(i,u,w);
ans+=solve(i,u,w);
check(i);
put(ans);putchar('\n');
}
return ;
}
