强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 i 都有一个感受能力值Ri ，小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离 dist(i,j) ≤ Ri + Rj，其中 dist(i, j)表示在这个树上从 i 到 j 的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 1开始编号。由于强强非常好奇， 你必须在他每次出现新节点后马上给出总共的朋友对数，不能拖延哦。
共有 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。
包含 n 行，每行输出1 个整数， 表示加入第 i 个点之后，树上有几对朋友。
1 #include<ctime> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #define lll tr[spc].ls 7 #define rrr tr[spc].rs 8 typedef long long lnt; 9 const double alpha=0.77; 10 struct pnt{ 11 int hd; 12 int F; 13 int T; 14 int dp; 15 int val; 16 int wgt; 17 int wgt_; 18 int fa[20]; 19 int root; 20 int root_; 21 lnt dis; 22 bool vis; 23 }p[2000000]; 24 struct ent{ 25 int twd; 26 int lst; 27 int vls; 28 }e[2000000]; 29 struct trnt{ 30 int ls; 31 int rs; 32 int val; 33 int wgt; 34 int rnd; 35 }tr[10000000],BLANK_TRNT; 36 int siz; 37 int top; 38 int cnt; 39 int tot; 40 int tms; 41 int root; 42 int maxval; 43 int n,test_no; 44 lnt lastans; 45 int bin[10000000]; 46 void del(int &spc) 47 { 48 if(!spc)return ; 49 bin[++top]=spc; 50 spc=0; 51 return ; 52 } 53 int newp(void) 54 { 55 if(top) 56 { 57 int spc=bin[top--]; 58 if(lll)bin[++top]=lll; 59 if(rrr)bin[++top]=rrr; 60 return spc; 61 } 62 return ++siz; 63 } 64 int apply(int v) 65 { 66 int spc=newp(); 67 tr[spc]=BLANK_TRNT; 68 tr[spc].val=v; 69 tr[spc].rnd=rand(); 70 tr[spc].wgt=1; 71 return spc; 72 } 73 void pushup(int spc) 74 { 75 tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+1; 76 return ; 77 } 78 void lturn(int &spc) 79 { 80 int tmp=lll; 81 lll=tr[tmp].rs; 82 tr[tmp].rs=spc; 83 pushup(spc); 84 pushup(tmp); 85 spc=tmp; 86 return ; 87 } 88 void rturn(int &spc) 89 { 90 int tmp=rrr; 91 rrr=tr[tmp].ls; 92 tr[tmp].ls=spc; 93 pushup(spc); 94 pushup(tmp); 95 spc=tmp; 96 } 97 void insert(int &spc,int v) 98 { 99 if(!spc) 100 { 101 spc=apply(v); 102 return ; 103 } 104 if(tr[spc].val<v) 105 { 106 insert(rrr,v); 107 if(tr[rrr].rnd<tr[spc].rnd)rturn(spc); 108 }else{ 109 insert(lll,v); 110 if(tr[lll].rnd<tr[spc].rnd)lturn(spc); 111 } 112 pushup(spc); 113 return ; 114 } 115 int rank(int spc,int v) 116 { 117 int ans=0; 118 while(spc) 119 { 120 if(tr[spc].val<v) 121 { 122 ans+=tr[lll].wgt+1; 123 spc=rrr; 124 }else spc=lll; 125 } 126 return ans; 127 } 128 //------------^Treap 129 void ade(int f,int t,int v) 130 { 131 if(!f||!t)return ; 132 cnt++; 133 e[cnt].twd=t; 134 e[cnt].vls=v; 135 e[cnt].lst=p[f].hd; 136 p[f].hd=cnt; 137 return ; 138 } 139 void decode(int &tmp_a) 140 { 141 tmp_a^=(lastans%1000000000); 142 return ; 143 } 144 int lca(int x,int y) 145 { 146 if(p[x].dp<p[y].dp)std::swap(x,y); 147 for(int i=17;i>=0;i--) 148 if(p[p[x].fa[i]].dp>=p[y].dp) 149 x=p[x].fa[i]; 150 if(x==y)return x; 151 for(int i=17;i>=0;i--) 152 { 153 if(p[x].fa[i]!=p[y].fa[i]) 154 { 155 x=p[x].fa[i]; 156 y=p[y].fa[i]; 157 } 158 } 159 return p[x].fa[0]; 160 } 161 lnt dis(int x,int y) 162 { 163 return p[x].dis+p[y].dis-p[lca(x,y)].dis*2; 164 } 165 void kill(int x,int f,int t) 166 { 167 tot++; 168 p[x].wgt_=0; 169 p[x].T=tms; 170 p[x].vis=false; 171 del(p[x].root); 172 del(p[x].root_); 173 for(int i=p[x].hd;i;i=e[i].lst) 174 { 175 int to=e[i].twd; 176 if(to==f||p[to].wgt_>t)continue; 177 kill(to,x,t); 178 } 179 return ; 180 } 181 void grc_dfs(int x,int f) 182 { 183 p[x].wgt=1; 184 int maxs=0; 185 for(int i=p[x].hd;i;i=e[i].lst) 186 { 187 int to=e[i].twd; 188 if(to==f||p[to].vis)continue; 189 grc_dfs(to,x); 190 p[x].wgt+=p[to].wgt; 191 maxs=std::max(maxs,p[to].wgt); 192 } 193 maxs=std::max(maxs,tot-p[x].wgt); 194 if(maxs<maxval) 195 { 196 root=x; 197 maxval=maxs; 198 } 199 return ; 200 } 201 void bin_dfs(int x,int F) 202 { 203 p[x].F=F; 204 p[x].vis=true; 205 int tmpv=tot; 206 for(int i=p[x].hd;i;i=e[i].lst) 207 { 208 int to=e[i].twd; 209 if(p[to].vis)continue; 210 if(p[x].wgt>p[to].wgt)tot=p[to].wgt; 211 else tot=tmpv-p[x].wgt; 212 root=0; 213 maxval=0x3f3f3f3f; 214 grc_dfs(to,to); 215 bin_dfs(root,x); 216 } 217 return ; 218 } 219 void relive(int x,int f,int F) 220 { 221 for(int i=x;i!=F;i=p[i].F) 222 { 223 p[i].wgt_++; 224 insert(p[i].root,dis(x,i)-p[x].val); 225 if(!p[i].F)break; 226 insert(p[i].root_,dis(p[i].F,x)-p[x].val); 227 } 228 for(int i=p[x].hd;i;i=e[i].lst) 229 { 230 int to=e[i].twd; 231 if(p[to].T!=tms||to==f)continue; 232 relive(to,x,F); 233 } 234 return ; 235 } 236 void rebuild(int x) 237 { 238 tms++; 239 int F=p[x].F; 240 tot=0; 241 root=0; 242 maxval=0x3f3f3f3f; 243 kill(x,x,p[x].wgt_); 244 grc_dfs(x,x); 245 bin_dfs(root,F); 246 relive(x,x,F); 247 return ; 248 } 249 void T_insert(int x) 250 { 251 int plc=0; 252 p[x].wgt_=1; 253 insert(p[x].root,-p[x].val); 254 for(int i=x;p[i].F;i=p[i].F) 255 { 256 insert(p[p[i].F].root,dis(p[i].F,x)-p[x].val); 257 insert(p[i].root_,dis(p[i].F,x)-p[x].val); 258 p[p[i].F].wgt_++; 259 if(1.00*p[i].wgt_>alpha*p[p[i].F].wgt_)plc=p[i].F; 260 } 261 if(plc)rebuild(plc); 262 return ; 263 } 264 lnt T_query(int x) 265 { 266 lnt ans=rank(p[x].root,p[x].val+1)-1; 267 for(int i=x;p[i].F;i=p[i].F) 268 { 269 ans+=rank(p[p[i].F].root,p[x].val-dis(p[i].F,x)+1); 270 ans-=rank(p[i].root_,p[x].val-dis(p[i].F,x)+1); 271 } 272 return ans; 273 } 274 int main() 275 { 276 scanf("%d",&test_no); 277 scanf("%d",&n); 278 for(int i=1;i<=n;i++) 279 { 280 p[i].vis=true; 281 int a,b,c; 282 scanf("%d%d%d",&a,&b,&c); 283 decode(a); 284 p[i].F=a; 285 p[i].val=c; 286 p[i].dp=p[a].dp+1; 287 p[i].dis=p[a].dis+b; 288 if(i!=1)p[i].fa[0]=a; 289 else p[i].fa[0]=1; 290 for(int j=1;j<=17;j++)p[i].fa[j]=p[p[i].fa[j-1]].fa[j-1]; 291 ade(i,a,b);ade(a,i,b); 292 T_insert(i); 293 lastans+=T_query(i); 294 printf("%lld\n",lastans); 295 } 296 return 0; 297 }
BZOJ3435: [Wc2014]紫荆花之恋(替罪羊树，Treap)
原文：https://www.cnblogs.com/blog-Dr-J/p/10447487.html