https://www.luogu.org/problemnew/show/P3920
参考博客：https://www.cnblogs.com/Khada-Jhin/p/10078584.html
于是写了替罪羊树，但无论怎么调参都会T，UOJ上是80分。
别忘记给 vis 赋值！！！
更新答案和更新点分树一起做会错？总之分开写了；
注意空间。
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
typedef long long ll;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Max(int x,int y){return x>y?x:y;}
int const xn=1e5+,inf=1e9,xm=;
int n,hd[xn],ct,to[xn<<],nxt[xn<<],r[xn],fa[xn],dep[xn],f[xn][];
int tot,rt[xn],frt[xn],siz[xn*xm],ls[xn*xm],rs[xn*xm];//
int size[xn],root,mx,sta[xn*xm],top;//sta
int v[xn*xm],d[xn];//v
ll ans;
vector<int>pt[xn];
bool vis[xn];
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=;i>=;i--)
if(dep[f[x][i]]>=dep[y])x=f[x][i];
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
if(x==y)return x; return f[x][];
}
int dist(int x,int y){return d[x]+d[y]-*d[lca(x,y)];}
int node(){if(top)return sta[top--]; return ++tot;}
int *flag,tmp[xn*xm],tp;//flag
void dfsx(int x)
{
if(!x)return;
dfsx(ls[x]); tmp[++tp]=x; dfsx(rs[x]);
}
void solve(int &x,int l,int r)
{
if(l>r){x=; return;}
int mid=((l+r)>>); x=tmp[mid];
if(l==r){ls[x]=rs[x]=; siz[x]=; return;}
solve(ls[x],l,mid-); solve(rs[x],mid+,r);
siz[x]=siz[ls[x]]+siz[rs[x]]+;
}
void rebuild(int &x)
{
tp=; dfsx(x);
solve(x,,tp);
}
void ins(int &x,int val)
{
if(!x){x=node(); v[x]=val; siz[x]=; return;}
siz[x]++;
if(val<=v[x])ins(ls[x],val);
else ins(rs[x],val);
if(siz[x]*<=Max(siz[ls[x]],siz[rs[x]])*)flag=&x;//
}
void insert(int &x,int val)
{
flag=; ins(x,val);
if(flag)rebuild(*flag);//
}
void del(int &x)
{
if(!x)return;
del(ls[x]); del(rs[x]);
siz[x]=v[x]=; sta[++top]=x; x=;
}
void getrt(int x,int ff,int sum)
{
int nmx=; size[x]=;
for(int i=hd[x],u;i;i=nxt[i])
{
if(vis[u=to[i]]||u==ff)continue;
getrt(u,x,sum); size[x]+=size[u];
nmx=Max(nmx,size[u]);
}
nmx=Max(nmx,sum-size[x]);
if(mx>nmx)mx=nmx,root=x;
}
void dfs(int x,int ff)
{
size[x]=; pt[root].pb(x);
insert(rt[root],r[x]-dist(x,root));
if(fa[root])insert(frt[root],r[x]-dist(x,fa[root]));
for(int i=hd[x],u;i;i=nxt[i])
if(!vis[u=to[i]]&&u!=ff)dfs(u,x),size[x]+=size[u];
}
void build(int x,int ff,int sum)
{
vis[x]=;
del(rt[x]); del(frt[x]);
fa[x]=ff; pt[x].clear();//
dfs(x,);
for(int i=hd[x],u;i;i=nxt[i])
{
if(vis[u=to[i]])continue;
//int ns=(size[u]>size[x]?sum-size[x]:size[u]);
int ns=size[u];
mx=inf; getrt(u,,ns); build(root,x,ns);
}
}
int find(int x,int val)
{
if(!x)return ;
if(val<=v[x])return siz[x]-siz[ls[x]]+find(ls[x],val);
else return find(rs[x],val);
}
/*
void work(int x)
{
int fl=0;
rt[x]=node(); v[rt[x]]=r[x]; vis[x]=1;//
for(int y=x;y;y=fa[y])
{
size[y]++; pt[y].pb(x);
ll ds=dist(x,y),ds2;
ans+=find(rt[y],ds-r[x]);
if(fa[y])ans-=find(frt[y],(ds2=dist(x,fa[y]))-r[x]);
if(fa[y]==y)exit(0);//--------
insert(rt[y],r[x]-ds);
if(fa[y])insert(frt[y],r[x]-ds2);
if(fa[y]&&size[y]*10>(size[fa[y]]+1)*9)fl=fa[y];
}
if(fl)
{
for(int i=0;i<pt[fl].size();i++)vis[pt[fl][i]]=0;
mx=inf; getrt(fl,0,size[fl]); build(root,fa[fl],size[fl]);
}
}
*/
ll query(int x)
{
ll ret=;
for(int y=x;y;y=fa[y])ret+=find(rt[y],dist(x,y)-r[x]);
for(int y=x;fa[y];y=fa[y])ret-=find(frt[y],dist(x,fa[y])-r[x]);
return ret;
}
void work(int x)
{
int fl=-;
for(int y=x;y;y=fa[y])
{
size[y]++; pt[y].pb(x);
insert(rt[y],r[x]-dist(x,y));
if(fa[y])insert(frt[y],r[x]-dist(x,fa[y]));
if(fa[y]&&size[y]*>(size[fa[y]]+)*)fl=fa[y];//
}
if(fl!=-)
{
for(int i=;i<pt[fl].size();i++)vis[pt[fl][i]]=;
int sum=size[fl];//
mx=inf; getrt(fl,,sum); build(root,fa[fl],sum);
}
}
void init(int x,int ff,int w)
{
f[x][]=ff; d[x]=d[ff]+w; dep[x]=dep[ff]+; vis[x]=;//vis!!!
for(int i=;i<&&f[f[x][i-]][i-];i++)f[x][i]=f[f[x][i-]][i-];
}
int gt[],gtp;
void wr(ll x)
{
if(!x){puts(""); return;}
if(x<)putchar('-'),x=-x; gtp=;
while(x)gt[++gtp]=x%,x/=;
for(int i=gtp;i;i--)putchar(gt[i]+'');
puts("");
}
int main()
{
int T=rd(); n=rd(); ll lst=;
rd(); rd(); r[]=rd(); vis[]=; size[]=; dep[]=;//
insert(rt[],r[]); pt[].pb(); puts("");
for(int i=,x,w;i<=n;i++)
{
x=(rd()^(lst%inf)); w=rd(); r[i]=rd();
add(x,i); add(i,x);
init(i,x,w); fa[i]=x; //work(i);
ans+=query(i);
//printf("%lld\n",lst=ans);
wr(lst=ans);
work(i);
}
return ;
}