題目描述

強(qiáng)強(qiáng)和萌萌是一對(duì)好朋友。有一天他們?cè)谕饷骈e逛，突然看到前方有一棵紫荊樹(shù)。這已經(jīng)是紫荊花飛舞的季節(jié)了，無(wú)數(shù)的花瓣以肉眼可見(jiàn)的速度從紫荊樹(shù)上長(zhǎng)了出來(lái)。仔細(xì)看看的話，這個(gè)大樹(shù)實(shí)際上是一個(gè)帶權(quán)樹(shù)。每個(gè)時(shí)刻它會(huì)長(zhǎng)出一個(gè)新的葉子節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)上有一個(gè)可愛(ài)的小精靈，新長(zhǎng)出的節(jié)點(diǎn)上也會(huì)同時(shí)出現(xiàn)一個(gè)新的小精靈。小精靈是很萌但是也很脆弱的生物，每個(gè)小精靈 i 都有一個(gè)感受能力值Ri ，小精靈 i, j 成為朋友當(dāng)且僅當(dāng)在樹(shù)上 i 和 j 的距離 dist(i,j) ≤ Ri + R! ，其中 dist(i, j)表示在這個(gè)樹(shù)上從 i 到 j 的唯一路徑上所有邊的邊權(quán)和。強(qiáng)強(qiáng)和萌萌很好奇每次新長(zhǎng)出一個(gè)葉子節(jié)點(diǎn)之后，這個(gè)樹(shù)上總共有幾對(duì)朋友。??
我們假定這個(gè)樹(shù)一開(kāi)始為空，節(jié)點(diǎn)按照加入的順序從 1開(kāi)始編號(hào)。由于強(qiáng)強(qiáng)非常好奇， 你必須在他每次出現(xiàn)新節(jié)點(diǎn)后馬上給出總共的朋友對(duì)數(shù)，不能拖延哦。?

輸入

共有 n + 2 行。?
第一行包含一個(gè)正整數(shù)，表示測(cè)試點(diǎn)編號(hào)。?
第二行包含一個(gè)正整數(shù) n ，表示總共要加入的節(jié)點(diǎn)數(shù)。?
我們令加入節(jié)點(diǎn)前的總共朋友對(duì)數(shù)是 last_ans，在一開(kāi)始時(shí)它的值為0。?
接下來(lái) n 行中第 i 行有三個(gè)數(shù) ai, bi, ri，表示節(jié)點(diǎn)? i? 的父節(jié)點(diǎn)的編號(hào)為 ai xor (last_ans mod 10^9)?? (其中xor 表示異或，mod? 表示取余，數(shù)據(jù)保證這樣操作后得到的結(jié)果介于 1到i? –? 1之間)，與父節(jié)點(diǎn)之間的邊權(quán)為 ci，節(jié)點(diǎn) i 上小精靈的感受能力值為r!。?
注意 a1 = c1 = 0，表示 1 號(hào)點(diǎn)是根節(jié)點(diǎn)，對(duì)于 i > 1，父節(jié)點(diǎn)的編號(hào)至少為1。

輸出

包含 n 行，每行輸出1 個(gè)整數(shù)， 表示加入第 i 個(gè)點(diǎn)之后，樹(shù)上有幾對(duì)朋友。

樣例輸入

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

樣例輸出

0
1
2
4
7

提示

1<=Ci<=10000
Ai<=2*10^9
Ri<=10^9
N<=100000

?

經(jīng)過(guò)一天的卡常+優(yōu)化，經(jīng)過(guò)從非旋轉(zhuǎn)treap到旋轉(zhuǎn)treap到替罪羊樹(shù)的改進(jìn)，終于過(guò)掉了這個(gè)傳說(shuō)中的神仙題！

因?yàn)檫@道題比較繁瑣，我們分塊講解。

點(diǎn)分治

按照動(dòng)態(tài)點(diǎn)分治的常規(guī)套路，我們考慮對(duì)于一棵給定的樹(shù)，單次詢問(wèn)如何用點(diǎn)分治處理。

當(dāng)以x為分治中心時(shí)，如果聯(lián)通塊中i,j兩個(gè)點(diǎn)滿足條件，假設(shè)i,j距離分治中心距離分別為di,dj，那么di+dj<=ri+rj，即di-ri<=rj-dj。

那么遍歷分治中心的每個(gè)子樹(shù)，記錄每個(gè)點(diǎn)的ri-di，對(duì)于每個(gè)點(diǎn)x找到有多少個(gè)點(diǎn)的ri-di>=dx-rx，同樣容斥去掉兩點(diǎn)位于同一棵子樹(shù)中的答案。

對(duì)于維護(hù)每個(gè)點(diǎn)的ri-di只要開(kāi)一棵平衡樹(shù)即可(因?yàn)楸绢}強(qiáng)制在線不能離散化，所以不能使用權(quán)值線段樹(shù))。

平衡樹(shù)

因?yàn)楸绢}用到的平衡樹(shù)功能單一，所以建議使用高速平衡樹(shù)(除非旋轉(zhuǎn)treap和splay之外的其他平衡樹(shù))。

當(dāng)然如果你有高超的卡常技巧也可以用splay或非旋轉(zhuǎn)treap。

對(duì)于高速平衡樹(shù)的選擇，個(gè)人建議選擇插入時(shí)間復(fù)雜度較優(yōu)的SBT或替罪羊樹(shù)(原因后面會(huì)說(shuō))。

對(duì)于替罪羊樹(shù)，經(jīng)過(guò)不懈嘗試，我發(fā)現(xiàn)重構(gòu)因子為0.86時(shí)的時(shí)間復(fù)雜度比較優(yōu)秀。

動(dòng)態(tài)點(diǎn)分治&點(diǎn)分樹(shù)

多次詢問(wèn)顯然要用點(diǎn)分樹(shù)來(lái)解決，通過(guò)上面對(duì)單次查詢點(diǎn)分治的處理方法，我們可以知道點(diǎn)分樹(shù)上每個(gè)點(diǎn)需要維護(hù)的信息：

1、每個(gè)點(diǎn)開(kāi)一棵平衡樹(shù)維護(hù)以它為分治中心時(shí)聯(lián)通塊內(nèi)所有點(diǎn)的ri-di(di為聯(lián)通塊內(nèi)點(diǎn)為到它的距離)。

2、每個(gè)點(diǎn)開(kāi)一棵平衡樹(shù)維護(hù)以它為分治中心時(shí)聯(lián)通塊內(nèi)所有點(diǎn)的ri-di(di為聯(lián)通塊內(nèi)點(diǎn)到它在點(diǎn)分樹(shù)上父節(jié)點(diǎn)的距離)。

那么顯然對(duì)于靜態(tài)的樹(shù)，單次修改和查詢只要從操作點(diǎn)往點(diǎn)分樹(shù)的根爬并對(duì)沿途點(diǎn)進(jìn)行修改或統(tǒng)計(jì)信息即可。

替罪羊式重構(gòu)

本題的重點(diǎn)是邊加點(diǎn)邊詢問(wèn)，那么問(wèn)題來(lái)了：如何構(gòu)建外層點(diǎn)分樹(shù)？

顯然不能加一個(gè)點(diǎn)重構(gòu)一次點(diǎn)分樹(shù)，而點(diǎn)分樹(shù)也不具有treap等平衡樹(shù)的可旋性，但是我們可以像替罪羊樹(shù)一樣重構(gòu)！

我們知道點(diǎn)分樹(shù)要求每個(gè)點(diǎn)的子樹(shù)中所有點(diǎn)都是以它為分治中心時(shí)能遍歷到的點(diǎn)，那么在新加一個(gè)點(diǎn)時(shí)我們不妨直接將這個(gè)點(diǎn)加到它原樹(shù)的父節(jié)點(diǎn)下面。

與替罪羊樹(shù)相同，我們同樣需要一個(gè)重構(gòu)因子，這里因?yàn)橹貥?gòu)時(shí)間復(fù)雜度較高，所以重構(gòu)因子建議設(shè)成0.9.

在往根方向修改沿途信息時(shí)我們記錄距離根最近的一個(gè)需要重構(gòu)的點(diǎn)，然后將這個(gè)子樹(shù)重構(gòu)。

因?yàn)檫@棵子樹(shù)在原樹(shù)上一定是一個(gè)聯(lián)通塊，所以直接對(duì)這個(gè)聯(lián)通塊進(jìn)行一遍點(diǎn)分治建出這個(gè)聯(lián)通塊真正的點(diǎn)分樹(shù)即可。

因?yàn)樾枰獙⒙?lián)通塊內(nèi)所有點(diǎn)的vis標(biāo)記都清空，所以還需要每個(gè)點(diǎn)開(kāi)一個(gè)vector存一下這個(gè)點(diǎn)在點(diǎn)分樹(shù)上的子樹(shù)中都有哪些點(diǎn)。

當(dāng)重構(gòu)外層點(diǎn)分樹(shù)時(shí)，因?yàn)辄c(diǎn)分樹(shù)上的父子關(guān)系改變，所以內(nèi)層平衡樹(shù)的信息也要發(fā)生相應(yīng)的變化。

因?yàn)橥鈱硬皇瞧胶鈽?shù)，我們無(wú)法像平衡樹(shù)一樣通過(guò)上傳來(lái)重新改變內(nèi)層信息，所以只能暴力刪除平衡樹(shù)并暴力重新插入信息。

這也是為什么要用插入時(shí)間復(fù)雜度較優(yōu)的平衡樹(shù)的原因。

LCA

同樣因?yàn)閯?dòng)態(tài)加點(diǎn)，無(wú)法用RMQ或者樹(shù)鏈剖分等方法求兩點(diǎn)在原樹(shù)的LCA，對(duì)于新加入的每個(gè)點(diǎn)，只能用倍增來(lái)求LCA。

時(shí)間復(fù)雜度

本題的時(shí)間復(fù)雜度主要在外層重構(gòu)及內(nèi)層平衡樹(shù)的重建上。

對(duì)于外層點(diǎn)分樹(shù)，重構(gòu)的時(shí)間復(fù)雜度每次均攤O(logn)。

對(duì)于內(nèi)層平衡樹(shù)的重建，因?yàn)槊總€(gè)平衡樹(shù)平均logn個(gè)節(jié)點(diǎn)，每次插入時(shí)間復(fù)雜度O(logn)，所以重建一棵平衡樹(shù)時(shí)間復(fù)雜度O(logn^2)。

一次內(nèi)層重建logn棵平衡樹(shù)時(shí)間復(fù)雜度是O(logn^3)。

同樣對(duì)于一次查詢或修改需要遍歷logn個(gè)節(jié)點(diǎn)，每次求LCA+平衡樹(shù)上查找時(shí)間復(fù)雜度O(logn)，單次查詢或修改時(shí)間復(fù)雜度O(logn^2)。

注意在點(diǎn)分治遞歸求重心時(shí)每層要dfs一遍整個(gè)聯(lián)通塊使當(dāng)前層的分治中心獲得真正的聯(lián)通塊大小，否則會(huì)影響重構(gòu)時(shí)的判斷。

綜上所述，總時(shí)間復(fù)雜度O(nlogn^3)。

#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; inline char _read() {static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read() {int x=0,f=1;char ch=_read();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=_read();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=_read();}return x*f; } int n; ll ans; int rot; int num; int tot; int cnt; int top; int type; int point; int x,y,z; int a,b,c; int r[100010]; int d[100010]; int f[100010]; int lg[100010]; int to[200010]; int mx[100010]; int dep[100010]; int vis[100010]; int root[100010]; int size[100010]; int head[100010]; int next[200010]; int st[4000010]; int froot[100010]; int g[100010][18]; vector<int>q[100010]; const int mod=1000000000; struct balance_tree {int cot;int *flag;int q[4000010];int v[4000010];int ls[4000010];int rs[4000010];int sum[4000010];inline bool bad(int rt){if(sum[rt]*86<=100*max(sum[ls[rt]],sum[rs[rt]])){return true;}return false;}inline void dfs(int rt){if(!rt){return ;}dfs(ls[rt]);q[++cot]=rt;dfs(rs[rt]);}inline void build(int &rt,int l,int r){int mid=(l+r)>>1;rt=q[mid];if(l==r){ls[rt]=rs[rt]=0;sum[rt]=1;return ;}if(l<mid){build(ls[rt],l,mid-1);}else{ls[rt]=0;}build(rs[rt],mid+1,r);sum[rt]=sum[ls[rt]]+sum[rs[rt]]+1;}inline void rebuild(int &rt){cot=0;dfs(rt);if(cot){build(rt,1,cot);}else{rt=0;}}inline void insert(int &rt,int k){if(!rt){if(top){rt=st[top--];}else{rt=++cnt;}v[rt]=k;sum[rt]=1;return ;}sum[rt]++;if(v[rt]>=k){insert(ls[rt],k);}else{insert(rs[rt],k);}if(bad(rt)){flag=&rt;}}inline void ins(int &rt,int val){flag=0;insert(rt,val);if(flag){rebuild(*flag);}}inline void del(int &rt){if(!rt){return ;}del(ls[rt]);del(rs[rt]);v[rt]=sum[rt]=0;st[++top]=rt;rt=0;}inline int query(int root,int k){int rt=root;int ans=0;while(rt){if(v[rt]>=k){rt=ls[rt];}else{ans+=sum[ls[rt]]+1;rt=rs[rt];}}return sum[root]-ans;} }tr; inline void add(int x,int y) {next[++tot]=head[x];head[x]=tot;to[tot]=y; } inline int lca(int x,int y) {if(d[x]<d[y]){swap(x,y);}int deep=d[x]-d[y];for(int i=0;i<=lg[deep];i++){if((deep&(1<<i))){x=g[x][i];}}if(x==y){return x;}for(int i=lg[d[x]];i>=0;i--){if(g[x][i]!=g[y][i]){x=g[x][i];y=g[y][i];}}return g[x][0]; } inline int dis(int x,int y) {return dep[x]+dep[y]-(dep[lca(x,y)]<<1); } inline void getroot(int x,int fa) {size[x]=1;mx[x]=0;for(int i=head[x];i;i=next[i]){if(!vis[to[i]]&&to[i]!=fa){getroot(to[i],x);size[x]+=size[to[i]];mx[x]=max(mx[x],size[to[i]]);}}mx[x]=max(mx[x],num-size[x]);if(mx[x]<mx[rot]){rot=x;} } inline void dfs(int x,int fa,int rt) {size[x]=1;q[rt].push_back(x);tr.ins(root[rt],r[x]-dis(x,rt));if(f[rt]){tr.ins(froot[rt],r[x]-dis(x,f[rt]));}for(int i=head[x];i;i=next[i]){if(!vis[to[i]]&&to[i]!=fa){dfs(to[i],x,rt);size[x]+=size[to[i]];}} } inline void partation(int x,int fa) {getroot(x,0);tr.del(root[x]);tr.del(froot[x]);q[x].clear();f[x]=fa;vis[x]=1;dfs(x,0,x);for(int i=head[x];i;i=next[i]){if(!vis[to[i]]){num=size[to[i]];rot=0;getroot(to[i],0);partation(rot,x);}} } inline void insert(int x) {point=-1;for(int i=x;i;i=f[i]){q[i].push_back(x);tr.ins(root[i],r[x]-dis(x,i));if(f[i]){tr.ins(froot[i],r[x]-dis(x,f[i]));}size[i]++;if(f[i]&&size[i]*100>(size[f[i]]+1)*90){point=f[i];}}if(point!=-1){int len=q[point].size();for(int i=0;i<len;i++){vis[q[point][i]]=0;}num=size[point];rot=0;getroot(point,0);partation(rot,f[point]);} } inline int query(int x) {int res=0;for(int i=x;i;i=f[i]){res+=tr.query(root[i],dis(x,i)-r[x]);}for(int i=x;f[i];i=f[i]){res-=tr.query(froot[i],dis(x,f[i])-r[x]);}return res; } int main() {type=read();n=read();x=read();y=read();z=read();printf("0\n");r[1]=z;tr.ins(root[1],r[1]);q[1].push_back(1);mx[0]=1<<30;size[1]=vis[1]=1;for(int i=2;i<=n;i++){lg[i]=lg[i>>1]+1;x=read();y=read();z=read();x^=(ans%mod);r[i]=z;add(i,x);add(x,i);g[i][0]=f[i]=x;d[i]=d[x]+1;dep[i]=dep[x]+y;vis[i]=1;for(int j=1;(1<<j)<=d[i];j++){g[i][j]=g[g[i][j-1]][j-1];}ans+=query(i);printf("%lld\n",ans);insert(i);} }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/10078584.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3435[Wc2014]紫荆花之恋——动态点分治(替罪羊式点分树套替罪羊树)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。