題意：給定一棵樹，每次詢問給出l r z，求在[l,r]區間內的每個節點i與z的最近公共祖先的深度之和

題解：

顯然，暴力求解的復雜度是無法承受的。

考慮這樣的一種暴力，我們把 z 到根上的點全部打標記，對于 l 到 r 之間的點，向上搜索到第一個有標記的點求出它的深度統計答案。觀察到，深度其實就是上面有幾個已標記了的點（包括自身）。所以，我們不妨把 z 到根的路徑上的點全部 +1，對于 l 到 r 之間的點詢問他們到根路徑上的點權和。仔細觀察上面的暴力不難發現，實際上這個操作具有疊加性，且可逆。也就是說我們可以對于 l 到 r 之間的點 i，將 i 到根的路徑上的點全部 +1, 轉而詢問 z 到根的路徑上的點（包括自身）的權值和就是這個詢問的答案。把詢問差分下，也就是用 [1, r] ? [1, l ? 1] 來計算答案，那么現在我們就有一個明顯的解法。從 0 到 n ? 1 依次插入點 i，即將 i 到根的路徑上的點全部+1。離線詢問答案即可。我們現在需要一個數據結構來維護路徑加和路徑求和，顯然樹鏈剖分或LCT 均可以完成這個任務。樹鏈剖分的復雜度為 O((n + q)· log n · log n)，LCT的復雜度為 O((n + q)· log n)，均可以完成任務。至此，題目已經被我們完美解決。（by gconeice）

沒考慮到取余之后會變負數，WA*2。這一點可以用(ans+P)%P來解決。

?

#include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define ll long longconst int MAXN=50000+2; const int P=201314; struct QUERY{int l,r,z; }q[MAXN]; struct HASH{int u;HASH *next;HASH(){}HASH(int _u,HASH *_next):u(_u),next(_next){} }mem[MAXN*2]; struct NODE{int c,f,son,mark,depth,belong;HASH *child; }node[MAXN]; typedef struct TREE{ll s;int l,r,add;TREE *lchild,*rchild;TREE(){}TREE(int _l,int _r):l(_l),r(_r),s(0),add(0),lchild(0),rchild(0){} } *ROOT; ROOT root; int N,Q,cnt; ll ans[MAXN]; vector<int> a[MAXN];void Insert(int u,int v){ node[u].child=&(mem[cnt++]=HASH(v,node[u].child));}void DFS1(int x,int f,int d){node[x].f=f,node[x].depth=d,node[x].c=1,node[x].son=-1;for(HASH *p=node[x].child;p;p=p->next)if(p->u!=f){DFS1(p->u,x,d+1);node[x].c+=node[p->u].c;if(node[x].son==-1 || node[p->u].c>node[node[x].son].c) node[x].son=p->u;} }void DFS2(int x,int b){node[x].belong=b,node[x].mark=++cnt;if(node[x].son==-1) return;DFS2(node[x].son,b);for(HASH *p=node[x].child;p;p=p->next)if(p->u!=node[x].son && p->u!=node[x].f) DFS2(p->u,p->u); }void Build(ROOT &x,int l,int r){x=new TREE(l,r);if(l==r) return;int m=(l+r)>>1;Build(x->lchild,l,m),Build(x->rchild,m+1,r); }void Pushup(ROOT &x){ x->s=(x->lchild->s+x->rchild->s)%P;}void Pushdown(ROOT &x,int m){if(x->add){x->lchild->s=(x->lchild->s+x->add*(m-(m>>1)))%P;x->rchild->s=(x->rchild->s+x->add*(m>>1))%P;x->lchild->add=(x->lchild->add+x->add)%P;x->rchild->add=(x->rchild->add+x->add)%P;x->add=0;} }void Change(ROOT &x,int l,int r){if(x->l>=l && x->r<=r){x->s=(x->s+x->r-x->l+1)%P,x->add=(x->add+1)%P;if(x->l!=x->r) Pushdown(x,x->r-x->l+1);return;}Pushdown(x,x->r-x->l+1);int m=(x->l+x->r)>>1;if(l<=m) Change(x->lchild,l,r);if(r>m) Change(x->rchild,l,r);Pushup(x); }void Update(int u){while(u!=-1){Change(root,node[node[u].belong].mark,node[u].mark);u=node[node[u].belong].f;} }ll Summation(ROOT &x,int l,int r){if(x->l>=l && x->r<=r) return x->s;Pushdown(x,x->r-x->l+1);int m=(x->l+x->r)>>1;ll ret=0;if(l<=m) ret=(ret+Summation(x->lchild,l,r))%P;if(r>m) ret=(ret+Summation(x->rchild,l,r))%P;return ret; }int Query(int u){ll ret=0;while(u!=-1){ret=(ret+Summation(root,node[node[u].belong].mark,node[u].mark))%P;u=node[node[u].belong].f;}return ret; }int main(){scanf("%d %d",&N,&Q);for(int i=1,u;i<N;i++){scanf("%d",&u);Insert(i,u),Insert(u,i);}for(int i=1;i<=Q;i++){scanf("%d %d %d",&q[i].l,&q[i].r,&q[i].z),q[i].l--;a[q[i].l].push_back(i),a[q[i].r].push_back(i);}cnt=0,DFS1(0,-1,0),DFS2(0,0);Build(root,1,N);for(int i=0;i<N;i++){Update(i);for(int j=0;j<a[i].size();j++){ll t=Query(q[a[i][j]].z);ans[a[i][j]]=(ans[a[i][j]]?t-ans[a[i][j]]:t)%P;ans[a[i][j]]=(ans[a[i][j]]+P)%P;}}for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);return 0; } View Code

?

轉載于:https://www.cnblogs.com/WDZRMPCBIT/p/6444259.html

總結

以上是生活随笔為你收集整理的BZOJ3626 LNOI2014 LCA 树链剖分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。