![BZOJ3435: [Wc2014]紫荆花之恋(替罪羊树，Treap)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "BZOJ3435: [Wc2014]紫荆花之恋(替罪羊树，Treap)")
Description
强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i 都有一个感受能力值Ri ，小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离 dist(i,j) ≤ Ri + Rj，其中 dist(i, j)表示在这个树上从 i 到 j 的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇， 你必须在他每次出现新节点后马上给出总共的朋友对数，不能拖延哦。
Input
共有 n + 2 行。
第一行包含一个正整数，表示测试点编号。
第二行包含一个正整数 n ，表示总共要加入的节点数。
我们令加入节点前的总共朋友对数是 last_ans，在一开始时它的值为0。
接下来 n 行中第 i 行有三个数 ai, bi, ri，表示节点 i 的父节点的编号为 ai xor (last_ans mod 10^9) (其中xor 表示异或，mod 表示取余，数据保证这样操作后得到的结果介于 1到i – 1之间)，与父节点之间的边权为 ci，节点 i 上小精灵的感受能力值为ri。
注意 a1 = c1 = 0，表示 1 号点是根节点，对于 i > 1，父节点的编号至少为1。
Output
包含 n 行，每行输出1 个整数， 表示加入第 i 个点之后，树上有几对朋友。
Sample Input
0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4
Sample Output
0
1
2
4
7
1
2
4
7
解题思路：
这道题毒瘤就在于强制在线，假设树是一开始给出的，就是将每个点新的贡献算出来，这个就是淀粉树。
现在考虑如何维护信息，现在分析一下这个式子，求$dis(i,j)\leq r_i+r_j$,在淀粉树上就是$dis(i,t)+dis(t,j)\leq r_i+r_j$
移项得到$r_i-dis(t,i) \geq dis(t,j)-r_j$,在淀粉中心维护一下容斥一下和那个震波就一样了。
只不过这里的计数是考虑比$r_i-dis(t,i)$小的$dis(t,j)-r_j$个数,维护$dis(t,j)$，查询$r_i-dis(t,i)$排名就好了。
这里的淀粉树不可以直接建出来。但是树高是log级别的，像替罪羊一样重构就好了。
卡常略微恶心，BZOJ上卡过了，luogu上开了O3调了半天$\alpha$最后0.77才过。
代码：
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define lll tr[spc].ls
#define rrr tr[spc].rs
typedef long long lnt;
const double alpha=0.77;
struct pnt{
int hd;
int F;
int T;
int dp;
int val;
int wgt;
int wgt_;
int fa[];
int root;
int root_;
lnt dis;
bool vis;
}p[];
struct ent{
int twd;
int lst;
int vls;
}e[];
struct trnt{
int ls;
int rs;
int val;
int wgt;
int rnd;
}tr[],BLANK_TRNT;
int siz;
int top;
int cnt;
int tot;
int tms;
int root;
int maxval;
int n,test_no;
lnt lastans;
int bin[];
void del(int &spc)
{
if(!spc)return ;
bin[++top]=spc;
spc=;
return ;
}
int newp(void)
{
if(top)
{
int spc=bin[top--];
if(lll)bin[++top]=lll;
if(rrr)bin[++top]=rrr;
return spc;
}
return ++siz;
}
int apply(int v)
{
int spc=newp();
tr[spc]=BLANK_TRNT;
tr[spc].val=v;
tr[spc].rnd=rand();
tr[spc].wgt=;
return spc;
}
void pushup(int spc)
{
tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;
return ;
}
void lturn(int &spc)
{
int tmp=lll;
lll=tr[tmp].rs;
tr[tmp].rs=spc;
pushup(spc);
pushup(tmp);
spc=tmp;
return ;
}
void rturn(int &spc)
{
int tmp=rrr;
rrr=tr[tmp].ls;
tr[tmp].ls=spc;
pushup(spc);
pushup(tmp);
spc=tmp;
}
void insert(int &spc,int v)
{
if(!spc)
{
spc=apply(v);
return ;
}
if(tr[spc].val<v)
{
insert(rrr,v);
if(tr[rrr].rnd<tr[spc].rnd)rturn(spc);
}else{
insert(lll,v);
if(tr[lll].rnd<tr[spc].rnd)lturn(spc);
}
pushup(spc);
return ;
}
int rank(int spc,int v)
{
int ans=;
while(spc)
{
if(tr[spc].val<v)
{
ans+=tr[lll].wgt+;
spc=rrr;
}else spc=lll;
}
return ans;
}
//------------^Treap
void ade(int f,int t,int v)
{
if(!f||!t)return ;
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void decode(int &tmp_a)
{
tmp_a^=(lastans%);
return ;
}
int lca(int x,int y)
{
if(p[x].dp<p[y].dp)std::swap(x,y);
for(int i=;i>=;i--)
if(p[p[x].fa[i]].dp>=p[y].dp)
x=p[x].fa[i];
if(x==y)return x;
for(int i=;i>=;i--)
{
if(p[x].fa[i]!=p[y].fa[i])
{
x=p[x].fa[i];
y=p[y].fa[i];
}
}
return p[x].fa[];
}
lnt dis(int x,int y)
{
return p[x].dis+p[y].dis-p[lca(x,y)].dis*;
}
void kill(int x,int f,int t)
{
tot++;
p[x].wgt_=;
p[x].T=tms;
p[x].vis=false;
del(p[x].root);
del(p[x].root_);
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f||p[to].wgt_>t)continue;
kill(to,x,t);
}
return ;
}
void grc_dfs(int x,int f)
{
p[x].wgt=;
int maxs=;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f||p[to].vis)continue;
grc_dfs(to,x);
p[x].wgt+=p[to].wgt;
maxs=std::max(maxs,p[to].wgt);
}
maxs=std::max(maxs,tot-p[x].wgt);
if(maxs<maxval)
{
root=x;
maxval=maxs;
}
return ;
}
void bin_dfs(int x,int F)
{
p[x].F=F;
p[x].vis=true;
int tmpv=tot;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].vis)continue;
if(p[x].wgt>p[to].wgt)tot=p[to].wgt;
else tot=tmpv-p[x].wgt;
root=;
maxval=0x3f3f3f3f;
grc_dfs(to,to);
bin_dfs(root,x);
}
return ;
}
void relive(int x,int f,int F)
{
for(int i=x;i!=F;i=p[i].F)
{
p[i].wgt_++;
insert(p[i].root,dis(x,i)-p[x].val);
if(!p[i].F)break;
insert(p[i].root_,dis(p[i].F,x)-p[x].val);
}
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].T!=tms||to==f)continue;
relive(to,x,F);
}
return ;
}
void rebuild(int x)
{
tms++;
int F=p[x].F;
tot=;
root=;
maxval=0x3f3f3f3f;
kill(x,x,p[x].wgt_);
grc_dfs(x,x);
bin_dfs(root,F);
relive(x,x,F);
return ;
}
void T_insert(int x)
{
int plc=;
p[x].wgt_=;
insert(p[x].root,-p[x].val);
for(int i=x;p[i].F;i=p[i].F)
{
insert(p[p[i].F].root,dis(p[i].F,x)-p[x].val);
insert(p[i].root_,dis(p[i].F,x)-p[x].val);
p[p[i].F].wgt_++;
if(1.00*p[i].wgt_>alpha*p[p[i].F].wgt_)plc=p[i].F;
}
if(plc)rebuild(plc);
return ;
}
lnt T_query(int x)
{
lnt ans=rank(p[x].root,p[x].val+)-;
for(int i=x;p[i].F;i=p[i].F)
{
ans+=rank(p[p[i].F].root,p[x].val-dis(p[i].F,x)+);
ans-=rank(p[i].root_,p[x].val-dis(p[i].F,x)+);
}
return ans;
}
int main()
{
scanf("%d",&test_no);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
p[i].vis=true;
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
decode(a);
p[i].F=a;
p[i].val=c;
p[i].dp=p[a].dp+;
p[i].dis=p[a].dis+b;
if(i!=)p[i].fa[]=a;
else p[i].fa[]=;
for(int j=;j<=;j++)p[i].fa[j]=p[p[i].fa[j-]].fa[j-];
ade(i,a,b);ade(a,i,b);
T_insert(i);
lastans+=T_query(i);
printf("%lld\n",lastans);
}
return ;
}