题目描述
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
输入输出格式
输入格式:
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
输出格式:
对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
输入输出样例
输入样例#1:
5 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3
输出样例#1:
6913
说明
对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不
会超过 10^6 。
树链剖分。
代码实现:
1 #include2 #include 3 #define ls k*2 4 #define rs k*2+1 5 #define LL long long 6 #define maxn 100010 7 using namespace std; 8 LL a,b,c,ans; 9 LL n,m,l,hs,nl;10 LL s[maxn],h[maxn];11 LL k[maxn],f[maxn],d[maxn],p[maxn],sz[maxn],is[maxn],ct[maxn];12 struct node{LL s,n;}e[maxn<<1];13 struct tree{LL l,r,s,f;}t[maxn<<2];14 inline void add(LL x,LL y){e[++hs]=(node){y,h[x]};h[x]=hs;}15 void dfs1(LL x,LL y,LL st){16 f[x]=y;d[x]=st;sz[x]=1;17 for(LL i=h[x];i;i=e[i].n)18 if(e[i].s!=y){19 dfs1(e[i].s,x,st+1);20 sz[x]+=sz[e[i].s];21 if(sz[e[i].s]>sz[is[x]]) is[x]=e[i].s;22 }23 }24 void dfs2(LL x){25 s[++l]=k[x];p[x]=l;26 if(is[x]){27 ct[is[x]]=ct[x];28 dfs2(is[x]);29 }30 for(LL i=h[x];i;i=e[i].n)31 if(e[i].s!=f[x]&&e[i].s!=is[x]){32 ct[e[i].s]=e[i].s;33 dfs2(e[i].s);34 }35 }36 void build(LL k,LL l,LL r){37 t[k].l=l;t[k].r=r;38 if(l==r){t[k].s=s[++nl];return;}39 LL mid=(l+r)>>1;40 build(ls,l,mid);41 build(rs,mid+1,r);42 t[k].s=t[ls].s+t[rs].s;43 }44 void heritage(LL k){45 t[ls].s+=(t[ls].r-t[ls].l+1)*t[k].f,t[ls].f+=t[k].f;46 t[rs].s+=(t[rs].r-t[rs].l+1)*t[k].f,t[rs].f+=t[k].f;47 t[k].f=0;48 }49 void change(LL k,LL l,LL r,LL al,LL ar,LL am){50 if(l==al&&r==ar){t[k].f+=am,t[k].s+=(r-l+1)*am;return;}51 if(t[k].f) heritage(k);52 LL mid=(l+r)>>1;53 if(al<=mid) change(ls,t[ls].l,t[ls].r,al,min(ar,mid),am);54 if(ar>mid) change(rs,t[rs].l,t[rs].r,max(al,mid+1),ar,am);55 t[k].s=t[ls].s+t[rs].s;56 }57 LL query(LL k,LL l,LL r,LL al,LL ar){58 if(l==al&&r==ar) return t[k].s;59 if(t[k].f) heritage(k);60 LL mid=(l+r)>>1,ans=0;61 if(al<=mid) ans+=query(ls,t[ls].l,t[ls].r,al,min(ar,mid));62 if(ar>mid) ans+=query(rs,t[rs].l,t[rs].r,max(al,mid+1),ar);63 return ans;64 }65 int main(){66 scanf("%lld%lld",&n,&m);67 for(LL i=1;i<=n;i++) scanf("%lld",&k[i]);68 for(LL i=1;i
题目来源:洛谷