洛谷P3178 [HAOI2015]树上操作
2018-06-17 21:27:51来源:未知 阅读 ()
题目描述
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
输入输出格式
输入格式:
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
输出格式:
对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
输入输出样例
5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3
6 9 13
说明
对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不
会超过 10^6 。
树链剖分的裸题
每次暴力更改就好
注意这题需要开long long
#include<iostream> #include<cstdio> #include<cstring> #define ls k<<1 #define rs k<<1|1 #define LL long long using namespace std; const LL MAXN=1e6+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p1=(p2=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:++*p1; } inline LL read() { char c=getchar();LL x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();} return x*f; } LL root=1; struct node { LL u,v,w,nxt; }edge[MAXN]; LL head[MAXN]; LL num=1; inline void AddEdge(LL x,LL y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } struct Tree { LL l,r,f,w,siz; }T[MAXN]; LL a[MAXN],b[MAXN],tot[MAXN],idx[MAXN],deep[MAXN],son[MAXN],top[MAXN],fa[MAXN],cnt=0; void update(LL k) { T[k].w=T[ls].w+T[rs].w; } void PushDown(LL k) { if(!T[k].f) return ; T[ls].w+=T[k].f*T[ls].siz; T[rs].w+=T[k].f*T[rs].siz; T[ls].f+=T[k].f; T[rs].f+=T[k].f; T[k].f=0; } LL dfs1(LL now,LL f,LL dep) { deep[now]=dep; tot[now]=1; fa[now]=f; LL maxson=-1; for(LL i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==f) continue; tot[now]+=dfs1(edge[i].v,now,dep+1); if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v; } return tot[now]; } void dfs2(LL now,LL topf) { idx[now]=++cnt; a[cnt]=b[now]; top[now]=topf; if(!son[now]) return ; dfs2(son[now],topf); for(LL i=head[now];i!=-1;i=edge[i].nxt) if(!idx[edge[i].v]) dfs2(edge[i].v,edge[i].v); } void Build(LL k,LL ll,LL rr) { T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1; if(ll==rr) { T[k].w=a[ll]; return ; } LL mid=(ll+rr)>>1; Build(ls,ll,mid); Build(rs,mid+1,rr); update(k); } void PointAdd(LL k,LL pos,LL val) { if(T[k].l==T[k].r) { T[k].w+=val; return ; } PushDown(k); LL mid=(T[k].l+T[k].r)>>1; if(pos<=mid) PointAdd(ls,pos,val); if(pos>mid) PointAdd(rs,pos,val); update(k); } void IntervalAdd(LL k,LL ll,LL rr,LL val) { if(ll<=T[k].l&&T[k].r<=rr) { T[k].w+=T[k].siz*val; T[k].f+=val; return ; } PushDown(k); LL mid=(T[k].l+T[k].r)>>1; if(ll<=mid) IntervalAdd(ls,ll,rr,val); if(rr>mid) IntervalAdd(rs,ll,rr,val); update(k); } LL IntervalAsk(LL k,LL ll,LL rr) { LL ans=0; if(ll<=T[k].l&&T[k].r<=rr) { ans+=T[k].w; return ans; } PushDown(k); LL mid=(T[k].l+T[k].r)>>1; if(ll<=mid) ans+=IntervalAsk(ls,ll,rr); if(rr>mid) ans+=IntervalAsk(rs,ll,rr); return ans; } LL TreeSum(LL x,LL y) { LL ans=0; while(top[x]!=top[y])//不在同一条链内 { if(deep[top[x]]<deep[top[y]]) swap(x,y); ans+=IntervalAsk(1,idx[top[x]],idx[x]); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); ans+=IntervalAsk(1,idx[x],idx[y]); return ans; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); LL N=read(),M=read(); for(LL i=1;i<=N;i++) b[i]=read(); for(LL i=1;i<=N-1;i++) { LL x=read(),y=read(); AddEdge(x,y);AddEdge(y,x); } dfs1(root,0,1); dfs2(root,root); Build(1,1,N); while(M--) { LL opt=read(),x,val; if(opt==1) { x=read(),val=read(); PointAdd(1,idx[x],val); } else if(opt==2) { x=read(),val=read(); IntervalAdd(1,idx[x],idx[x]+tot[x]-1,val); } else { x=read(); printf("%lld\n",TreeSum(root,x)); } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash