Aragorn's Story HDU-3966 点权模板题

Posted on | Edited on | In , , | Views:
Symbols count in article: 3.7k | Reading time ≈ 3 mins.

题意

三种操作：

  1. c1 到 c2 链上都增加k
  2. c1 到 c2 链上都减少k
  3. 查询c1 到c2 链上的和

分析

轻重链剖分后用树状数组维护即可。

代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 5e4+5;
int a[maxn];
struct HLD {
    int n, dfn;
    int sz[maxn], top[maxn], son[maxn], dep[maxn], par[maxn], id[maxn],
        rk[maxn];
    vector<int> G[maxn];
    void init(int n) {
        this->n = n;
        clr(son, -1);
        clr(diff, 0);
        dfn = 0;
        for (int i = 0; i <= n; i++) G[i].clear();
    }
    void addedge(int u, int v) {
        G[u].pb(v);
        G[v].pb(u);
    }
    void dfs(int u, int fa, int d) {
        dep[u] = d;
        par[u] = fa;
        sz[u] = 1;
        for (auto &v : G[u]) {
            if (v == fa) continue;
            dfs(v, u, d + 1);
            sz[u] += sz[v];
            if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
        }
    }
    void link(int u, int t) {
        top[u] = t;
        id[u] = ++dfn;
        rk[dfn] = u;
        if (son[u] == -1) return;
        link(son[u], t);
        for (auto &v : G[u]) {
            if (v != son[u] && v != par[u]) link(v, v);
        }
    }
    void update_path(int u, int v, int val) {
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            update(id[top[u]], id[u], val);
            u = par[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        update(id[u], id[v], val);
    }

    int diff[maxn];

    int lowb(int x) { return x & (-x); }
    int query(int x) {
        int ret = 0;
        for (int i = x; i > 0; i -= lowb(i)) {
			ret += diff[i];
			continue;
		}
        return ret;
    }
    void update(int l, int r, int val) {
        for (int i = l; i <= n; i += lowb(i)) diff[i] += val;
        for (int i = r + 1; i <= n; i += lowb(i)) diff[i] -= val;
    }
};
HLD hld;

int main() {
// /*
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    // */
    std::ios::sync_with_stdio(false);
    int n, m, q;
    while (cin >> n >> m >> q) {
        hld.init(n + 5);
        for (int i = 1; i <= n; i++) cin >> a[i];
        int u, v, w;
        for (int i = 0; i < m; i++) {
            cin >> u >> v;
            hld.addedge(u, v);
        }
        hld.dfs(1, 1, 1);
        hld.link(1, 1);
        for (int i = 1; i <= n; i++) hld.update(hld.id[i], hld.id[i], a[i]);

        string op;
        for (int i = 0; i < q; i++) {
            cin >> op;
            if (op == "I") {
                cin >> u >> v >> w;
                hld.update_path(u, v, w);
            } else if (op == "D") {
                cin >> u >> v >> w;
                hld.update_path(u, v, -w);
            } else {
                cin >> u;
                cout << hld.query(hld.id[u]) << endl;
            }
        }
    }
}