HAOI 树上操作-白红宇

HAOI 树上操作

阅读量：6800 次

发布时间：2019-06-26

本文共 4071 字，大约阅读时间需要 13 分钟。

P1457 - 【HAOI2015】树上操作

Description

有一棵点数为N的树，以点1为根，且树点有边权。然后有M个操作，分为三种：

操作1：把某个节点x的点权增加a。

操作2：把某个节点x为根的子树中所有点的点权都增加a。

操作3：询问某个节点x到根的路径中所有点的点权和。

Input

第一行两个整数N,M，表示点数和操作数。

接下来一行N个整数，表示树中节点的初始权值。

接下来N-1行每行两个正整数fr,to，表示该树中存在一条边(fr,to)。

再接下来M行，每行分别表示一次操作。其中第一个数表示该操作的种类（1~3），之后接这个操作的参数（x或者x a）。

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

Sample Input

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

Sample Output

Hint

数据范围：

对于30%的数据，N,M<=1000。

对于50%的数据，N,M<=100000且数据随机。

对于100%的数据，N,M<=100000，且所有输入数据的绝对值都不会超过10^6。

Source

HAOI2015

分块，动态树

树链剖分裸题，做某个点子树内的操作，他所对应的区间是子树的根到子树内节点的ｄｆｎ最大值。

1 #define ll long long  2 #define ls o<<1  3 #define rs (o<<1)|1  4 #define mimi int mid=(L+R)>>1;  5 #define rep(i,a,b) for(register int i=a;i<=b;i++)  6 #include
       
          7 #include
        
           8 #include
         
            9 #include
          
            10 #include
           
             11 #include
            
              12 #include
             
               13 #include
              
                14 #include
               
                 15 #include
                
                  16 #include
                  17 #include
                  
                    18 using namespace std; 19 const int N=100010; 20 int gi(); 21 struct E{ 22 int to,net; 23 }e[N*2]; 24 int head[N],top[N],fa[N],dep[N],tid[N],pos[N],son[N],siz[N],qq[N],n,num_e,m,idx; 25 ll val[N],W[N],sum[N*4],lazy[N*4],len[N*4]; 26 void add(int x,int y) { 27 e[++num_e].to=y , e[num_e].net=head[x] , head[x]=num_e; 28 } 29 void dfs1(int x,int fu) { 30 siz[x]=1; 31 fa[x]=fu; 32 dep[x]=dep[fu]+1; 33 for(int i=head[x];i;i=e[i].net) 34 if(e[i].to!=fu){ 35 dfs1(e[i].to,x); 36 siz[x] +=siz[e[i].to]; 37 if(siz[e[i].to]>siz[son[x]]) son[x]=e[i].to; 38 } 39 } 40 void dfs2(int x,int tp) { 41 tid[x]=++idx; 42 pos[idx]=x; 43 top[x]=tp; 44 qq[x]=idx; 45 W[idx]=val[x]; 46 if(!son[x]) return; 47 dfs2(son[x],tp); 48 qq[x]=qq[son[x]]; 49 for(int i=head[x];i;i=e[i].net) { 50 int to=e[i].to; 51 if(to!=fa[x]&&to!=son[x]) { 52 dfs2(to,to); 53 qq[x]=max(qq[to],qq[x]); 54 } 55 } 56 } 57 void build(int o,int L,int R) { 58 len[o]=R-L+1; 59 if(L==R) { 60 sum[o]=W[L]; 61 return; 62 } 63 mimi 64 build(ls,L,mid); 65 build(rs,mid+1,R); 66 sum[o] =sum[ls] + sum[rs]; 67 } 68 void down(int); 69 void Update(int o,int L,int R,int p,int x) { 70 if(L!=R) down(o); 71 if(L==R&&L==p) { 72 sum[o]+=x; 73 return; 74 } 75 mimi 76 if(p<=mid) Update(ls,L,mid,p,x); 77 else Update(rs,mid+1,R,p,x); 78 sum[o] = sum[ls] + sum[rs]; 79 } 80 void down(int o) { 81 sum[ls] += len[ls] * lazy[o]; 82 sum[rs] += len[rs] * lazy[o]; 83 lazy[ls] += lazy[o] , lazy[rs] += lazy[o]; 84 lazy[o]=0; 85 } 86 void GG (int o,int L,int R,int l,int r,int det) { 87 if(L!=R) down(o); 88 if(l<=L&&R<=r) { 89 lazy[o] += det; 90 sum[o] += det * len[o]; 91 return; 92 } 93 mimi; 94 if(l<=mid) GG(ls,L,mid,l,r,det); 95 if(r>mid) GG(rs,mid+1,R,l,r,det); 96 sum[o] = sum[ls] + sum[rs]; 97 } 98 ll query(int o,int L,int R,int l,int r) { 99 if(L!=R) down(o);// don't forget it;100 ll tot=0;101 if(l<=L&&R<=r) return sum[o];102 mimi;103 if(l<=mid) tot += query(ls,L,mid,l,r);104 if(r>mid) tot += query(rs,mid+1,R,l,r);105 return tot;106 }107 ll solvesum(int x,int y) {108 ll ans=0;109 while(top[x]!=top[y]) {110 if(dep[top[x]]>dep[top[y]]) swap(x,y);111 ans += query(1,1,n,tid[top[y]],tid[y]);112 y=fa[top[y]];113 }114 if(dep[x]>dep[y]) swap(x,y);115 // if(x==y) return ans+val[x];116 ans += query(1,1,n,tid[x],tid[y]);117 return ans;118 }119 int main() {120 freopen("Alan.in","r",stdin);121 freopen("Alan.out","w",stdout);122 n=gi(),m=gi();123 rep(i,1,n) scanf("%lld",&val[i]);124 rep(i,1,n-1) {125 int x=gi(),y=gi();add(x,y),add(y,x);126 }127 dfs1(1,0);128 dfs2(1,1);129 build(1,1,n);130 int k;131 rep(i,1,m) {132 k=gi();133 int x=gi(),a;134 if(k==1) a=gi(),val[x]+=a,Update(1,1,n,tid[x],a);135 else if(k==2) a=gi(),GG(1,1,n,tid[x],qq[x],a);136 else printf("%lld\n",solvesum(1,x));137 }138 return 0;139 }140 141 int gi() {142 int res=0,f=1;143 char ch=getchar();144 while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();145 if(ch=='-') ch=getchar(),f=-1;146 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();147 return res*f;148 }