bzoj 3683: Falsita 樹鏈剖分+線段樹

2019-11-08 20:02:01

字體：大中小

來源：轉載

供稿：網友

題意

給出一棵有根樹，一開始每個節點都有一個權值。要求資瓷三個操作： S x delta節點x的權值增加delta M x delta以x為根的子樹的所有節點的權值增加delta Q x詢問(∑lca(p,q)==xv[p]+v[q])/(∑lca(p,q)==x) $(/sum_{lca(p,q)==x}v[p]+v[q])/(/sum lca(p,q)==x)$ n,m<=300000

分析

一開始覺得nlog2的算法過不了，其實跑的飛快。因為這題涉及到子樹和祖先的修改和詢問，所以直接就想到了樹剖。分母上的值顯然可以預處理，那么我們就考慮如何維護分子上的值。設sum[x]表示以x為根的子樹的權值和，那么分子上的值顯然就等于v[x]?(size[x]?1)+∑fa[y]==xsum[y]?(size[x]?size[y]) $v[x]*(size[x]-1)+/sum_{fa[y]==x}sum[y]*(size[x]-size[y])$ 我們直接用一個ans數組記錄每個節點的答案，現在考慮修改。首先先用線段樹維護樹剖。用一個數組nx[x]表示x所在的重鏈中x的子節點，沒有則為0 對于一個S操作，先修改當前點的答案，然后考慮如何維護其祖先的答案。對于一條需要修改的重鏈，除了其第一個節點外，不難發現其余節點的答案所修改的權值就是delta*(size[x]-size[nx[x]])，那么就可以先修改每條鏈的第一個點，其余節點就可以在線段樹上打標記啦。M操作除了先修改其子樹的答案然后把delta變為size[x]*delta其余同理。

代碼

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define LL long longusing namespace std;const int N=300005;int cnt,n,m,sz,tot,last[N],nx[N],bel[N],pos[N],fa[N],top[N],size[N],v[N],mn[N],mx[N],root;LL num[N],sum[N],ans[N];struct edge{int to,next;}e[N*2];struct tree{int l,r;LL tag1,tag2;}t[N*5];int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void addedge(int u,int v){ e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;}void dfs1(int x){ size[x]=1;sum[x]=v[x]; for (int i=last[x];i;i=e[i].next) { if (e[i].to==fa[x]) continue; dfs1(e[i].to); size[x]+=size[e[i].to]; sum[x]+=sum[e[i].to]; } ans[x]=(LL)v[x]*(size[x]-1);num[x]=size[x]-1; for (int i=last[x];i;i=e[i].next) { if (e[i].to==fa[x]) continue; ans[x]+=(LL)sum[e[i].to]*(size[x]-size[e[i].to]); num[x]+=(LL)size[x]*size[e[i].to]-(LL)size[e[i].to]*size[e[i].to]; }}void dfs2(int x,int chain){ pos[x]=++sz;bel[sz]=x;top[x]=chain;mx[x]=mn[x]=sz;int k=0; for (int i=last[x];i;i=e[i].next) if (e[i].to!=fa[x]&&size[e[i].to]>size[k]) k=e[i].to; if (!k) return; dfs2(k,chain); nx[x]=k; for (int i=last[x];i;i=e[i].next) if (e[i].to!=fa[x]&&e[i].to!=k) dfs2(e[i].to,e[i].to); mx[x]=sz;}void pushdown(int d,int l,int r){ if (l==r) return; int mid=(l+r)/2; if (!t[d].l) t[d].l=++tot; if (!t[d].r) t[d].r=++tot; if (t[d].tag1!=0) { LL w=t[d].tag1; t[t[d].l].tag1+=w;t[t[d].r].tag1+=w; if (l==mid) ans[bel[l]]+=(LL)w*(size[bel[l]]-size[nx[bel[l]]]); if (mid+1==r) ans[bel[r]]+=(LL)w*(size[bel[r]]-size[nx[bel[r]]]); t[d].tag1=0; } if (t[d].tag2!=0) { LL w=t[d].tag2; t[t[d].l].tag2+=w;t[t[d].r].tag2+=w; if (l==mid) ans[bel[l]]+=(LL)num[bel[l]]*w; if (mid+1==r) ans[bel[r]]+=(LL)num[bel[r]]*w; t[d].tag2=0; }}void ins1(int &d,int l,int r,int x,int y,LL w){ if (!d) d=++tot; pushdown(d,l,r); if (l==x&&r==y) { if (l==r) ans[bel[l]]+=(LL)w*(size[bel[l]]-size[nx[bel[l]]]); else t[d].tag1+=w; return; } int mid=(l+r)/2; if (y<=mid) ins1(t[d].l,l,mid,x,y,w); else if (x>mid) ins1(t[d].r,mid+1,r,x,y,w); else { ins1(t[d].l,l,mid,x,mid,w); ins1(t[d].r,mid+1,r,mid+1,y,w); }}void ins2(int &d,int l,int r,int x,int y,LL w){ if (!d) d=++tot; pushdown(d,l,r); if (l==x&&r==y) { if (l==r) ans[bel[l]]+=(LL)num[bel[l]]*w; else t[d].tag2+=w; return; } int mid=(l+r)/2; if (y<=mid) ins2(t[d].l,l,mid,x,y,w); else if (x>mid) ins2(t[d].r,mid+1,r,x,y,w); else { ins2(t[d].l,l,mid,x,mid,w); ins2(t[d].r,mid+1,r,mid+1,y,w); }}void solve(int op,int u,int delta){ if (op==1) ans[u]+=(LL)delta*(size[u]-1); else ins2(root,1,n,mn[u],mx[u],delta); if (u==1) return; int ls;LL w; if (op==1) w=delta; else w=(LL)delta*size[u]; if (u!=top[u]) { u=fa[u]; ins1(root,1,n,pos[top[u]],pos[u],w); ls=top[u];u=fa[top[u]]; } else { ls=u;u=fa[u]; } while (u) { ans[u]+=(LL)w*(size[u]-size[ls]); if (u==top[u]) { ls=u;u=fa[u];continue; } u=fa[u]; ins1(root,1,n,pos[top[u]],pos[u],w); ls=top[u];u=fa[top[u]]; }}int main(){ n=read();m=read(); for (int i=2;i<=n;i++) { fa[i]=read(); addedge(i,fa[i]); } for (int i=1;i<=n;i++) v[i]=read(); dfs1(1); dfs2(1,1); for (int i=1;i<=m;i++) { char ch[2]; scanf("%s",ch); if (ch[0]=='S'||ch[0]=='M') { int u=read(),delta=read(); if (ch[0]=='S') solve(1,u,delta); else solve(2,u,delta); } else { int u=read(); ins1(root,1,n,pos[u],pos[u],0); if (!num[u])