树

Posted on Edited on In

题目大意：现在有一棵树，共 N 个节点。规定: 根节点为 1 号节点，且每个节点有一个点权。现在，有 M 个操作需要在树上完成，每次操作为下列三种之一：1 x a：操作 1，将节点 x 点权增加 a。2 x a：操作 2，将以节点 x 为根的子树中所有点的权值增加 a。3 x：操作 3，查询节点 x 到根节点的路径中所有点的点权和

树剖板子题

细节：开ll，但是尽量不要define int long long容易超时，空间也可能爆炸

代码如下：

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 66;
int n, m;

ll a[N], v[N];
int fa[N], siz[N], son[N], dep[N];
int dfn[N], top[N], tot;

struct SEGMENTTREE
{
    ll len, tag, dat;
}tree[N << 2];

inline void dfs1(int x, int yhm_fa)
{
    int i, y;
    siz[x] = 1;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == yhm_fa) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y, x);
        siz[x] += siz[y];
        if (siz[y] > siz[son[x]]) son[x] = y;
    }
    return;
}

inline void dfs2(int x, int yhm_top)
{
    dfn[x] = ++ tot, a[tot] = v[x];
    top[x] = yhm_top;
    if (! son[x]) return;
    dfs2(son[x], yhm_top);
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
    return;
}

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1;
    return (void)(tree[p].dat = tree[l].dat + tree[r].dat);
}

inline void down(int p)
{
    int l = p << 1, r = (p << 1) | 1; ll c = tree[p].tag;
    if (! c) return;
    tree[l].tag += c, tree[l].dat += tree[l].len * c;
    tree[r].tag += c, tree[r].dat += tree[r].len * c;
    return (void)(tree[p].tag = 0);
}

inline void build(int p, int l, int r)
{
    tree[p].len = (r - l + 1);
    if (l == r) return (void)(tree[p].dat = a[l]);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int nl, int nr, ll c)
{
    if (nl <= l && nr >= r)
    {
        tree[p].tag += c;
        tree[p].dat += tree[p].len * c;
        return;
    }
    down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) updata(p << 1, l, mid, nl, nr, c);
    if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, c);
    return (void)(up(p));
}

inline ll query(int p, int l, int r, int nl, int nr)
{
    if (nl <= l && nr >= r) return tree[p].dat;
    down(p);
    int mid = (l + r) >> 1; ll res = 0;
    if (nl <= mid) res = query(p << 1, l, mid, nl, nr);
    if (nr > mid) res += query((p << 1) | 1, mid + 1, r, nl, nr);
    return res;
}

inline ll query_path(int x, int y)
{
    ll res = 0;
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    res += query(1, 1, n, dfn[y], dfn[x]);
    return res;
}

signed main()
{
    freopen("t1.in", "r", stdin), freopen("t1.out", "w", stdout);
    int i, x, y, opt;
    n = read(), m = read();
    for (i = 1; i <= n; ++ i) v[i] = read();
    for (i = 1; i < n; ++ i)
    {
        x = read(), y = read();
        add_edge(x, y), add_edge(y, x);
    }

    dfs1(1, 0), dfs2(1, 1);
    build(1, 1, n);
/*
{
    for (i = 1; i <= n; ++ i) cout << dfn[i] << ' ';
    cout << '\n';
    for (i = 1; i <= n; ++ i) cout << son[i] << ' ';
    cout << '\n';
    for (i = 1; i <= n; ++ i) cout << top[i] << ' ';
    cout << '\n';
    cout << "--------------------------------\n";
}
*/
    for (i = 1; i <= m; ++ i)
    {
        opt = read(), x = read();
        if (opt == 1) y = read(), updata(1, 1, n, dfn[x], dfn[x], y);
        if (opt == 2) y = read(), updata(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
        if (opt == 3) put(query_path(1, x));
    }
    return 0;
}