Description

给你一棵nn个节点的树，初始权值为AiA_i，需要支持三种操作：

  • 把(u,v)(u,v)这条链上的所有点权值+x+x，与这条链相邻的所有点权值+y+y
  • 查询xx的权值
  • 查询xx权值的历史最大值

Constraints

n,m≤105n,m\le 10^5

Solution

首先考虑如何用维护历史最大值，区间修改单点查询

线段树维护两个tag：now表示当前的加法标记，max表示加法标记的最大值

注意，这里的两个tag都是还未下传的，只要下传就都要设为0

下面是push_down的代码：

1
2
3
4
5
6
7
8
inline void push_down (int root)
{
	if (!Tree[root].now && !Tree[root].max) return ;
	Chkmax(ls.max, ls.now + Tree[root].max);
	Chkmax(rs.max, rs.now + Tree[root].max);
	ls.now += Tree[root].now, rs.now += Tree[root].now;
	Tree[root].now = Tree[root].max = 0;
}

接下来考虑如何做这道题

不难发现，链上信息可以直接树剖维护，而其相邻点的信息就其实是轻儿子信息

考虑稍微改变一下剖分方法，把所有轻儿子按照父亲的 dfsdfs 序排序

感性理解一下就是先自顶向下遍历重链上的每个重儿子，全部遍历完后再自顶向下遍历重链上每个重儿子的轻儿子。 代码如下：

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
void work1(int o) {
	id[o] = ++clk;
	if (son[o]) work1(son[o]);
}

void work2(int o) {
	idl[o] = clk + 1;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o] || u == son[o]) continue;
		id[u] = ++clk;
	}
	idr[o] = clk;
	if (son[o]) work2(son[o]);
}

void DFS_decompose(int o) {
	if (son[fa[o]] == o) top[o] = top[fa[o]]; 
	else {
		top[o] = o;
		if (son[o]) work1(son[o]);
		work2(o);
	}
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o]) continue;
		DFS_decompose(u);
	}
}

其中work1是遍历重儿子，work2是遍历轻儿子，DFS_decompose是整个剖分的过程

这样剖分过后，就能很好地在线段树上维护重链的一段轻儿子的信息了（因为是连续的）

有一些很多很骚的细节见代码注释

Code(from dy0607)

由于dy的代码实在是写得太好了，忍不住直接贴他的了

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)
#define Forr(i, j, k) for (int i = j; i >= k; i--)

const int N = 1e5 + 10;

using namespace std;

struct Info {
	int mx, cur;
	
	Info operator + (Info b) const {
		return (Info){max(cur + b.mx, mx), cur + b.cur};
	}
};

int val[N];

struct Segment_Tree {

	Info A[N << 2];

	#define lc (o << 1)
	#define rc (o << 1 | 1)
	#define M ((L + R) >> 1)	

	void build(int o, int L, int R) {
		if (L == R) A[o] = (Info){val[L], val[L]};
		else build(lc, L, M), build(rc, M + 1, R);
	}

	void pushdown(int o) {
		A[lc] = A[lc] + A[o], A[rc] = A[rc] + A[o];
		A[o] = (Info){0, 0};
	}

	void add(int o, int L, int R, int l, int r, Info w) {
		if (l <= L && R <= r) A[o] = A[o] + w;
		else {
			pushdown(o);
			if (l <= M) add(lc, L, M, l, r, w);
			if (r > M) add(rc, M + 1, R, l, r, w);
		}
	}

	void add(int o, int L, int R, int l, int r, int w) {
		add(o, L, R, l, r, (Info){w, w});
	}

	Info query(int o, int L, int R, int x) {
		if (L == R) return A[o];
		else {
			pushdown(o);
			return x <= M ? query(lc, L, M, x) : query(rc, M + 1, R, x);
		}
	}

}T;

int Begin[N], Next[N << 1], to[N << 1], e;

void add(int u, int v) {
	to[++e] = v, Next[e] = Begin[u], Begin[u] = e;
}

int n, m;
int A[N];

int fa[N], sz[N], son[N], dep[N];

void DFS_init(int o) {
	sz[o] = 1;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o]) continue;
		fa[u] = o, dep[u] = dep[o] + 1;
		DFS_init(u);
		sz[o] += sz[u];
		if (sz[u] > sz[son[o]]) son[o] = u;
	}
}

int top[N], id[N], idl[N], idr[N], clk;

void work1(int o) {
	id[o] = ++clk;
	if (son[o]) work1(son[o]);
}

void work2(int o) {
	idl[o] = clk + 1;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o] || u == son[o]) continue;
		id[u] = ++clk;
	}
	idr[o] = clk;
	if (son[o]) work2(son[o]);
}

void DFS_decompose(int o) {
	if (son[fa[o]] == o) top[o] = top[fa[o]]; 
	else {
		top[o] = o;
		if (son[o]) work1(son[o]);
		work2(o);
	}
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (u == fa[o]) continue;
		DFS_decompose(u);
	}
}

int main() {

	freopen("t.in", "r", stdin);
	freopen("t.out", "w", stdout);

	scanf("%d%d", &n, &m);
	For(i, 1, n) scanf("%d", &A[i]);
	For(i, 2, n) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	
	dep[1] = 1;
	DFS_init(1);
	id[1] = clk = 1;
	DFS_decompose(1);

	For(i, 1, n) val[id[i]] = A[i];
	T.build(1, 1, n);

	while (m--) {
		int ty;
		scanf("%d", &ty);
		if (!ty) {
			int u, v, x, y;
			scanf("%d%d%d%d", &u, &v, &x, &y);

			vector<int> vec;
			while (top[u] != top[v]) {
				int a = top[u], b = top[v];
				if (dep[a] < dep[b]) swap(a, b), swap(u, v);
				if (u != a) T.add(1, 1, n, id[son[a]], id[u], x);
				if (y >= 0) T.add(1, 1, n, id[a], id[a], x - y);
				else vec.push_back(id[a]);
				/*
				   对于每一个重链顶端(除了询问链的最底部)的点，它都会在158行被算+y的贡献，但它实际贡献是+x，所以在149行需要算x-y的贡献
				   那为什么要讨论y的正负呢？
				   假设某个点权值本来为3,如果+2再-2的话，历史最大值就变成了5，而实际上这个+2再-2的操作是不存在的
				   所以需要判断y的正负，若y>=0则先-y，再+y；若y<0则先+y,再-y。这样就能保证先往小的更新，再边大，就不会影响历史最大值
				*/
				if (idl[a] <= idr[u]) T.add(1, 1, n, idl[a], idr[u], y); // 轻儿子信息更新
				if (son[u]) T.add(1, 1, n, id[son[u]], id[son[u]], y);
				u = fa[a];
			}
			if (dep[u] > dep[v]) swap(u, v);

			if (u == top[u]) {
				T.add(1, 1, n, id[u], id[u], x);
				if (u != v) T.add(1, 1, n, id[son[u]], id[v], x);
			} else {
				T.add(1, 1, n, id[u], id[v], x);
			}
			/*
			   上面要把重链的顶部单独考虑
			   这是因为重链的顶端会作为它父亲的某个轻儿子被遍历到，所以重链的顶端和这条重链下面的部分是不一定连续的
			*/
			if (idl[u] <= idr[v]) T.add(1, 1, n, idl[u], idr[v], y);
			if (son[v]) T.add(1, 1, n, id[son[v]], id[son[v]], y);
			if (fa[u]) T.add(1, 1, n, id[fa[u]], id[fa[u]], y);
			for (int o : vec) T.add(1, 1, n, o, o, x - y); 
		} else {
			int x;
			scanf("%d", &x);
			Info ans = T.query(1, 1, n, id[x]);
			printf("%d\n", ty == 1 ? ans.cur : ans.mx);
		}
	}

	return 0;
}