BZOJ4034【HAOI2015】树上操作 <树链剖分>

Posted on Symbols count in article: 898 Reading time ≈ 3 mins.

Problem

【HAOI2015】树上操作

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

有一棵点数为 NN 的树，以点 11 为根，且树点有边权。然后有 MM 个
操作，分为三种：
操作 11 ：把某个节点 xx 的点权增加 aa 。
操作 22 ：把某个节点 xx 为根的子树中所有点的点权都增加 aa 。
操作 33 ：询问某个节点 xx 到根的路径中所有点的点权和。

Input

第一行包含两个整数 N,MN, M 。表示点数和操作数。接下来一行 NN 个整数，表示树中节点的初始权值。接下来 N−1N-1 行每行三个正整数 fr,tofr, to ， 表示该树中存在一条边 (fr,to)(fr, to) 。再接下来 MM 行，每行分别表示一次操作。其中第一个数表示该操作的种类(1∼3)(1\sim 3) ，之后接这个操作的参数(x 或者 x a)(x\ 或者\ x\ a) 。

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
6
9
13

HINT

对于 100%100\% 的数据， N,M≤105N,M\le 10^5 ，且所有输入数据的绝对值都不会超过 10610^6 。

标签：树链剖分

Solution

这是一道DFSDFS序的裸题。可以DFSDFS序++树状数组区间修改单点查询(差分)搞定。
但为了写板我码了个树剖。反正是裸题。
不多说。

Code

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
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
typedef long long lnt;
vector <int> G[MAX_N+5];
int n, m, rt, c[MAX_N+5], sz[MAX_N+5];
int dep[MAX_N+5], fa[MAX_N+5], son[MAX_N+5];
int into[MAX_N+5], outo[MAX_N+5], top[MAX_N+5], ind;
lnt seg[(MAX_N<<2)+5], tag[(MAX_N<<2)+5];
void DFS(int u) {
    sz[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];	if (v == fa[u])	continue;
        dep[v] = dep[u]+1, fa[v] = u, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v])	son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp, into[u] = ++ind;	if (son[u])	DFS(son[u], tp);
    for (int i = 0, v; i < G[u].size(); i++) {v = G[u][i];	if ((v^fa[u]) && (v^son[u]))	DFS(v, v);}
    outo[u] = ind;
}
void updata(int v) {seg[v] = seg[v<<1]+seg[v<<1|1];}
void downtag(int v, int s, int t) {
    if (!tag[v])	return;	int mid = s+t>>1;
    seg[v<<1] += tag[v]*(mid-s+1), seg[v<<1|1] += tag[v]*(t-mid);
    tag[v<<1] += tag[v], tag[v<<1|1] += tag[v], tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, lnt x) {
    if (s >= l && t <= r) {seg[v] += x*(t-s+1), tag[v] += x;	return;}
    int mid = s+t>>1;	downtag(v, s, t);
    if (l <= mid)	modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1)	modify(v<<1|1, mid+1, t, l, r, x);
    updata(v);	return;
}
lnt query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r)	return seg[v];
    int mid = s+t>>1;	lnt ret = 0;	downtag(v, s, t);
    if (l <= mid)	ret += query(v<<1, s, mid, l, r);
    if (r >= mid+1)	ret += query(v<<1|1, mid+1, t, l, r);
    updata(v);	return ret;
}
void solve1(int p, lnt x) {modify(1, 1, n, into[p], into[p], x);}
void solve2(int p, lnt x) {modify(1, 1, n, into[p], outo[p], x);}
void solve3(int p) {
    lnt ans = 0;
    while (top[p] != rt)	ans += query(1, 1, n, into[top[p]], into[p]), p = fa[top[p]];
    ans += query(1, 1, n, into[rt], into[p]);	printf("%lld\n", ans);
}
int main() {
    scanf("%d%d", &n, &m), rt = 1;	for (int i = 1; i <= n; i++)	scanf("%d", c+i);
    for (int i = 1, u, v; i < n; i++)	scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    DFS(rt), DFS(rt, rt);	for (int i = 1; i <= n; i++)	modify(1, 1, n, into[i], into[i], c[i]);
    while (m--) {
        int opt;	scanf("%d", &opt);
        if (opt == 1) {int p; lnt x;	scanf("%d%lld", &p, &x), solve1(p, x);}
        if (opt == 2) {int p; lnt x;	scanf("%d%lld", &p, &x), solve2(p, x);}
        if (opt == 3) {int p;	scanf("%d", &p), solve3(p);}
    }
    return 0;
}