(luogu3178)树上操作(HAOI2015) 发表于 2018-01-27 | 分类于 solution , 树相关 , 树链剖分 树链剖分第一题, 难度: 简单 树链剖分笔记索引 思路:树链剖分+线段树区间和 详细操作还是写在代码注释里好了 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165#include <cstdio>#include <iostream>#include <cctype>using namespace std;const int Mn(100005);long long qrd() //快读{ long long x(0),f(1); char c(getchar()); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x*f;}int n;struct edge //边表, 存树{ int e,nt;}ed[Mn*2];int vs[Mn],ec(0);long long d[Mn];void adde(int s,int e) //边表加边{ ed[++ec].e=e; ed[ec].nt=vs[s]; vs[s]=ec;}int dp[Mn],sz[Mn],pa[Mn],hs[Mn]; //深度, 子树大小, 父结点, 重儿子void dfs1(int x) //寻找重儿子{ sz[x] = 1; for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(!dp[ntn]) { dp[ntn] = dp[x]+1; pa[ntn] = x; dfs1(ntn); sz[x] += sz[ntn]; if(sz[hs[x]]<sz[ntn]) hs[x]=ntn; } }}struct tn //线段树的结点域{ int l,r; //区间左右端点 long long v,lt; //区间和, 懒标记}t[Mn<<2];int cd[Mn],tp[Mn],dc(0); //结点访问时间, 链顶, 时间戳long long a[Mn]; //剖分后的序列void dfs2(int x) //重儿子拉成链{ a[++dc] = d[x]; cd[x] = dc; if(hs[x]) tp[hs[x]]=tp[x], dfs2(hs[x]); for(int e(vs[x]);e;e=ed[e].nt) { int& ntn(ed[e].e); if(dp[ntn]>dp[x] && ntn!=hs[x]) tp[ntn] = ntn, dfs2(ntn); }}void bud(int l,int r,int rt) //构建线段树{ if(l==r) { t[rt].l=t[rt].r=l; t[rt].v=a[l]; return; } int mid((l+r)>>1); bud(l,mid,rt<<1); bud(mid+1,r,rt<<1|1); t[rt].l = l, t[rt].r = r; t[rt].v = t[rt<<1].v+t[rt<<1|1].v;}void pd(int rt) //下放标记{ if(t[rt].lt) { t[rt<<1].lt += t[rt].lt; t[rt<<1|1].lt += t[rt].lt; t[rt<<1].v += (t[rt<<1].r-t[rt<<1].l+1)*t[rt].lt; t[rt<<1|1].v += (t[rt<<1|1].r-t[rt<<1|1].l+1)*t[rt].lt; t[rt].lt = 0; }}void mdf(int rt,int ml,int mr,long long a) //线段树修改{ int& xl(t[rt].l),&xr(t[rt].r); if(xl>=ml && xr<=mr) { t[rt].v += (xr-xl+1)*a; t[rt].lt += a; return; } pd(rt); int mid((xl+xr)>>1); if(ml<=mid) mdf(rt<<1,ml,mr,a); if(mr>mid) mdf(rt<<1|1,ml,mr,a); t[rt].v = t[rt<<1].v+t[rt<<1|1].v;}long long qry(int rt,int ql,int qr) //线段树查询{ int& xl(t[rt].l),&xr(t[rt].r); if(xl>=ql && xr<=qr) return t[rt].v; pd(rt); int mid((xl+xr)>>1); long long ret(0); if(ql<=mid) ret += qry(rt<<1,ql,qr); if(qr>mid) ret += qry(rt<<1|1,ql,qr); return ret;}int main(){ n = qrd(); int m(qrd()); for(int i(1);i<=n;++i) d[i] = qrd(); for(int i(1);i<n;++i) { int x(qrd()),y(qrd()); adde(x,y), adde(y,x); } /*----初始化----*/ dp[1]=1,pa[1]=0,tp[1]=1; dfs1(1); dfs2(1); bud(1,n,1); /*--------*/ while(m--) { int o(qrd()),x; long long a; switch(o) { case 1: x=qrd(), a=qrd(); mdf(1,cd[x],cd[x],a); //更改单结点 break; case 2: x=qrd(), a=qrd(); mdf(1,cd[x],cd[x]+sz[x]-1,a); //更改子树 break; case 3: x=qrd(); long long ret(0); while(x) //重复查询从x结点到根节点的所有重链的和 { ret += qry(1,cd[tp[x]],cd[x]); x = pa[tp[x]]; } printf("%lld\n",ret); break; } } return 0;}