Talk is Cheap, Show Me the Code!

0%

动态差分

Posted on Edited on In

有n个点的一棵树，有m个操作，分为两类：
(1):1 x y d:把x到y路径上每个点的权值加d
(2):2 x:询问x点的权值

输入描述:

第一行两个整数n和m
接下来n-1行，每行两个整数，表示一条边
接下来m行，每行两个操作中的一个。
n,m<=10^5

输出描述:

对于每个2操作，输出结果。

示例1
输入

5 4
1 2
1 3
3 4
3 5
1 3 4 1
2 3
1 1 5 2
2 3

输出

1
3

说明

区别：动态回答询问

dongtaichafen.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// 每次修改路径，而非一个点, 区别于苹果树，同于找路径
// 要求动态回答询问， 区别于松鼠的新家，路径更新

// Two mistakes from LCA, (1) fa[N][S+2], (2) return after goUp.
#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;
const int S = 20;

int fa[N][S+2], dep[N];
int n,m;

int Lid[N], Rid[N], tot;

struct Node{
    int to, id;
};

typedef long long LL;

vector<Node>edges[N];

void dfs(int x, int f){
    Lid[x] = ++tot;
    fa[x][0] = f, dep[x] = dep[f]+ 1;
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i].to;
        if(y==f)continue;
        dfs(y, x);
    }
    Rid[x] = tot;
}

void goUp(int &x, int step){
    for(int i=0;i<=S;i++)
        if(step & (1<<i)) x = fa[x][i];
}

int lca(int a, int b){
    if(dep[a] < dep[b]) swap(a,b);
    goUp(a, dep[a]-dep[b]);
    if(a==b ) return a;
    for(int i=S;i>=0;i--)
        if(fa[a][i] != fa[b][i])
            a = fa[a][i], b= fa[b][i];
    return fa[a][0];
}

struct Bit{
    LL C[N];
    void add(int x, int d){
        while(x<=tot){
            C[x] += d;
            x += x&-x;
        }
    }
    LL sum(int x){
        int res = 0;
        while(x){
            res += C[x];
            x -= x&-x;
        }
        return res;
    }
}bit;

int main(){
    scanf("%d%d", &n ,&m);
    int a, b;
    for(int i=1;i<n;i++){
        scanf("%d%d", &a, &b);
        edges[a].push_back({b, i});
        edges[b].push_back({a, i});
    }

    dfs(1, 0);
    for(int j=1;j<=S;j++)
        for(int i=1;i<=n;i++) fa[i][j] = fa[ fa[i][j-1] ][j-1];

    int x, y, d;
    for(int i=1;i<=m;i++){
        scanf("%d", &a);
        if(a==1){
            scanf("%d%d%d", &x ,&y, &d);
            int c = lca(x, y);
//            printf("lca = %d %d %d\n", x, y, c);
            int e = fa[c][0];
            bit.add(Lid[x], d);
            bit.add(Lid[y], d);
            bit.add(Lid[c], -d);
            if(e)bit.add(Lid[e], -d); // if is crucial!
        }
        else{
            scanf("%d", &x);
            printf("%lld\n", bit.sum(Rid[x]) - bit.sum(Lid[x] -1));
        }
    }
    return 0;

}