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]) PRintf("%.6lf/n",0); else printf("%.6lf/n",(double)2.0*ans[u]/num[u]); } } return 0;}

上一篇：FPGA 学习笔记（十一） VGA驱动的实现

下一篇：Node.js npm uuid