正題

題目鏈接:https://www.lydsy.com/JudgeOnline/problem.php?id=3626

---

題目大意

一棵樹，每次給出$(l,r,z)$詢問$$\sum _{i=l}^{r}de{p}_{LCA(i,z)}$$

---

解題思路

若詢問$LCA(x,y)$的深度有一種方法，將$1～x$的路徑都打上標記，然后查詢$1～y$這條路徑上有多少個打了記號的點。

若查詢一個點$x$和很多個點的$LCA$深度和就可以對于每個點到根節點的路徑上$+1$，然后查詢$1～x$路徑上數字和即可。

所以我們可以將詢問$(l,r,z)$拆分成$(1,r,z)?(1,l?1,z)$，然后用指針掃過去，用樹鏈剖分維護樹上路徑和即可。

時間復雜度$O((n+Q){\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e4+10; struct Tree_node{ll w,lazy; }; struct Edge_node{ll to,next; }a[N]; struct node{ll x,y,val,id; }q[N*2]; struct Seq_Tree{Tree_node t[N*4];void Downdata(ll x,ll l,ll r){if(!t[x].lazy) return;ll mid=(l+r)/2;t[x*2].w+=t[x].lazy*(mid-l+1);t[x*2+1].w+=t[x].lazy*(r-mid);t[x*2].lazy+=t[x].lazy;t[x*2+1].lazy+=t[x].lazy;t[x].lazy=0;return;}void Change(ll k,ll l,ll r,ll x,ll y,ll val){if(l==x&&r==y){t[k].lazy+=val;t[k].w+=val*(r-l+1);return;}ll mid=(l+r)/2;Downdata(k,l,r);if(y<=mid) Change(k*2,l,mid,x,y,val);else if(x>mid) Change(k*2+1,mid+1,r,x,y,val);else Change(k*2,l,mid,x,mid,val),Change(k*2+1,mid+1,r,mid+1,y,val);t[k].w=t[k*2].w+t[k*2+1].w; }ll Ask(ll k,ll l,ll r,ll x,ll y){if(l==x&&r==y) return t[k].w;ll mid=(l+r)/2;Downdata(k,l,r);if(y<=mid) return Ask(k*2,l,mid,x,y);if(x>mid) return Ask(k*2+1,mid+1,r,x,y);return Ask(k*2,l,mid,x,mid)+Ask(k*2+1,mid+1,r,mid+1,y);} }T; ll n,m,cnt,tot,num,ans[N],ls[N],fa[N]; ll siz[N],seq[N],id[N],son[N],dep[N],top[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs1(ll x){siz[x]=1; for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;dep[y]=dep[x]+1;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;}return; } void dfs2(ll x){id[x]=++cnt;seq[cnt]=x;if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==son[x]) continue;top[y]=y;dfs2(y);} } void Change_path(ll x,ll y,ll num) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y); T.Change(1,1,n,id[top[x]],id[x],num);x=fa[top[x]];}if(dep[x]<dep[y]) swap(x,y);T.Change(1,1,n,id[y],id[x],num); } ll Ask_path(ll x,ll y) {ll ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=T.Ask(1,1,n,id[top[x]],id[x]);x=fa[top[x]];}if(dep[x]<dep[y]) swap(x,y);ans+=T.Ask(1,1,n,id[y],id[x]); return ans; } bool cmp(node x,node y) {return x.x<y.x;} int main() {scanf("%lld%lld",&n,&m);for(ll i=2;i<=n;i++){scanf("%lld",&fa[i]);fa[i]++;addl(fa[i],i);}dep[1]=1;dfs1(1);dfs2(1);for(ll i=1;i<=m;i++){ll l,r,z;scanf("%lld%lld%lld",&l,&r,&z);l++;r++;z++;q[++num]=(node){l-1,z,-1,i};q[++num]=(node){r,z,1,i};}sort(q+1,q+1+num,cmp);ll now=1;for(ll i=1;i<=num;i++){while(now<=q[i].x)Change_path(1,now,1),now++;ans[q[i].id]+=q[i].val*Ask_path(1,q[i].y);}for(ll i=1;i<=m;i++)printf("%lld\n",ans[i]%201314); }

總結

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

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