BZOJ---4034: [HAOI2015]樹上操作【樹鍊剖分】

題面：

BZOJ----4034：[HAOI2015]樹上操作

題意:

給定一顆樹，支援三種操作：（1）單點修改（2）兩點之間的最短路徑上的所有點修改（3）詢問兩點之間的最短路徑上的所有點的和

分析：

樹鍊剖分真是個好東西，巧妙地将一棵樹拍成線性的，這樣就容易用資料結構維護區間問題了，與普通區間操作不同的是，它将樹上兩點之間的路徑劃分為logN個編号連續的區間，然後對每個區間進行普通操作即可，是以一次操作為O(logn*logn)；樹鍊剖分也可以O(logn)求出LCA

代碼：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 2e5+15;
int cnt,head[maxn],op,n,m,u,v,val,a[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
inline void add(int u,int v){
    e[++cnt] = (edge){v,head[u]};
    head[u] = cnt;
}
int d[maxn],f[maxn],sz[maxn],son[maxn];
void dfs1(int x,int fa,int depth){
     f[x] = fa; d[x] = depth; sz[x] = 1;
     for(int i = head[x];i;i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v,x,depth+1); sz[x] += sz[v];
        if(sz[v] > sz[son[x]]) son[x] = v;
     } 
}
int rk[maxn],id[maxn],top[maxn],num;
void dfs2(int x,int Top){
    top[x] = Top; id[x] = ++num;
    rk[num] = x;
    if(!son[x]) return;
    dfs2(son[x],Top);
    for(int i = head[x];i;i = e[i].nxt){
        int v = e[i].to;
        if(v != son[x]&&v != f[x]) dfs2(v,v);
    }
}
/**************以上為樹鍊剖分****************/
LL tr[maxn<<2],lazy[maxn<<2];
inline void pushdown(int x,int l,int r){
    int mid = (l+r)>>1;
    tr[x<<1] = (tr[x<<1] + 1ll*(mid-l+1)*lazy[x]);
    tr[x<<1|1] = (tr[x<<1|1]+1ll*(r-mid)*lazy[x]);
    lazy[x<<1] = (lazy[x<<1] + lazy[x]);
    lazy[x<<1|1] = (lazy[x<<1|1]+lazy[x]);
    lazy[x] = 0;
}
void build(int l,int r,int x){
    if(l == r){
        tr[x] = a[rk[l]];
        return ;
    }
    int mid = (l+r) >> 1;
    build(l,mid,x<<1);
    build(mid+1,r,x<<1|1);
    tr[x] = (tr[x<<1]+tr[x<<1|1]);
}
void query(int l,int r,int L,int R,int x,LL &sum){
    if(l > R || r < L) return ;
    if(l >= L && r <= R){
        sum = (sum+tr[x]);
        return ;
     }
    if(lazy[x]) pushdown(x,l,r);
    int mid = (l+r)>>1;
    query(l,mid,L,R,x<<1,sum);
    query(mid+1,r,L,R,x<<1|1,sum);
}
void updata(int l,int r,int L,int R,int x,LL val){
    if(l > R || r < L) return ;
    if(l >= L && r <= R){
        tr[x] = (tr[x]+1ll*(r-l+1)*val);
        lazy[x] = (lazy[x]+val);
        return ;
    }
    if(lazy[x]) pushdown(x,l,r);
    int mid = (l+r)>>1;
    updata(l,mid,L,R,x<<1,val);
    updata(mid+1,r,L,R,x<<1|1,val);
    tr[x] = (tr[x<<1] + tr[x<<1|1]);
}
/***************以上為普通線段樹****************/
LL queryPath(int x,int y){
    LL sum = 0;
    while(top[x] != top[y]){
        if(d[top[x]] < d[top[y]]) swap(x,y);
        query(1,n,id[top[x]],id[x],1,sum);
        x = f[top[x]];
    }
    if(d[x] > d[y]) swap(x,y);
    query(1,n,id[x],id[y],1,sum);
    return sum;
}
void updataPath(int x,int y,LL val){
     while(top[x] != top[y]){
        if(d[top[x]] < d[top[y]]) swap(x,y);
        updata(1,n,id[top[x]],id[x],1,val);
        x = f[top[x]];
     }
     if(d[x] > d[y]) swap(x,y);
     updata(1,n,id[x],id[y],1,val);   
}
/**************以上為樹上兩點之間路徑的操作****************/
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n; ++i) scanf("%d",a+i);
    for(int i = 1;i < n; ++i) {
        scanf("%d %d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs1(1,0,1); dfs2(1,1); build(1,n,1);
    while(m--){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d %d",&u,&val);
            updata(1,n,id[u],id[u],1,val);
        }
        else if(op == 2){
            scanf("%d %d",&u,&val);
            updataSon(u,val);
        }
        else{
            scanf("%d",&u);
            printf("%lld\n",queryPath(1,u));
        }
    }
    return 0;
}