bzoj4034（dfs序+BIT/鍊剖+線段樹）

記得以前是用鍊剖+線段樹做的，在鍊剖的時候順便維護dfs序，思路簡單實作起來就有點麻煩了。。

回顧這題發現其實主要是2操作針對子樹而3操作針對鍊，而且唯一的詢問操作3的鍊其實是到根的權值和，那麼就想能不能直接dfs序進行操作呢？做一遍dfs序後我們可以用字首和求出權值和，操作1修改點權值就把貢獻限制在子樹内就可以，然而修改樹權值就感覺沒什麼思路了。。操作2對每個結點貢獻是t*(d[x]-d[f])，也就是每個結點修改的還不一樣，無法統一修改。。

上網找題解發現可以用2個BIT維護，對子樹中的結點貢獻還可以化為t*d[x]-t*d[f],由于t*d[f]恒定，是以可以類似操作1直接修改點權值，剩下的就再開一個BIT維護_t就可以了，詢問的時候直接乘上d[x]即可。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inf 1000000007
#define eps 1e-8
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define ls T[i<<1]
#define rs T[i<<1|1]
#define op T[i]
#define NM 100005
#define nm 200005
#define pi 3.141592653
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}


struct edge{int t;edge*next;}e[nm],*h[NM],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll a[2][NM],_y;
int in[NM],out[NM],d[NM],tot;
int n,m,_x,_t,b[NM];
void mod(int x,int k,ll t){while(x<=n)a[k][x]+=t,x+=lowbit(x);}
ll sum(int x,int k){return x?a[k][x]+sum(x-lowbit(x),k):0;}

void dfs(int x){
    in[x]=++tot;
    link(x)if(!in[j->t]){d[j->t]=d[x]+1;dfs(j->t);}
    out[x]=tot;
}

int main(){
    freopen("data.in","r",stdin);
    n=read();m=read();
    inc(i,1,n)b[i]=read();
    inc(i,1,n-1){_x=read();_y=read();add(_x,_y);add(_y,_x);}
    dfs(1);
    inc(i,1,n)mod(in[i],0,b[i]),mod(out[i]+1,0,-b[i]);
    while(m--){
        _t=read();_x=read();
        if(_t==3)printf("%lld\n",sum(in[_x],0)+sum(in[_x],1)*(d[_x]+1));
        else{
            _y=read();
            if(_t==1)mod(in[_x],0,_y),mod(out[_x]+1,0,-_y);
            else{
                mod(in[_x],1,_y);mod(out[_x]+1,1,-_y);
                mod(in[_x],0,-_y*d[_x]);mod(out[_x]+1,0,_y*d[_x]);
            }
        }
    }
    return 0;
}      

4034: [HAOI2015]樹上操作

Time Limit: 10 Sec  

Memory Limit: 256 MB

Submit: 6230  

Solved: 2061

[

​​Submit​​][

​​Status​​][

​​Discuss​​]

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

6

9

13

HINT

 對于 100% 的資料， N,M<=100000 ，且所有輸入資料的絕對值都不會超過 10^6 。

Source

​​鳴謝bhiaibogf提供​​

[

​​Submit​​][

​​Status​​][