序列——线段树维护矩阵转移

首先，我们需要普通 DP 方程改为矩阵乘法或广义矩阵乘法形式，可能会增加一些状态，然后用线段树维护矩阵乘法即可。

这个模型推荐使用横向量乘方阵的形式，可以直接从左往右乘。

树——重链剖分

原理

首先，记录每个节点的轻儿子对这个节点 DP 数组的贡献，然后用线段树维护一条重链。

对于一条重链，链底（一定是叶子节点）的矩阵一般是单位阵，其它节点的矩阵表示一个状态转移，初始的向量是一个关于链底的向量，用这个向量乘一个后缀之后，得到这个后缀开头节点的完整 DP 信息。

对于修改的节点，需要修改的有：

• 这个节点。
• 到根节点的轻边，轻边上父节点。

实现细节

修改时不可能直接求节点轻儿子对它的贡献，所以考虑增量，这就要求维护前后的两个 DP 信息，具体如下：

• 求当前链顶的信息。
• 进行上一个修改（当前节点的修改）。
• 求当前链顶信息。
• 用增量改变链顶的父节点的信息。
• 当前节点条到链顶的父节点。
• 当链顶节点为根，修改当前节点。

建议使用方阵乘列向量的方式，线段树维护时可以从左往右乘，但查询时要先查询右儿子，再查询左儿子。

卡常

• 对每条重链开线段树。
• 矩阵乘法循环展开，使用数组存矩阵，但注意 memset 的空间需要是一个具体矩阵的空间（而不是传的指针）。
• inline，快读。

参考代码（P4751）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, INF = 1e9;

int n, m, x[N];
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N], dep[N], size[N], son[N], top[N], End[N], id[N], rnk[N], dfst;
int g[N][2], f[N][2];
struct node{
	int l, r;
	int x[2][2];
}t[N * 4];
int root[N], pid;

inline void init(int x[][2])
{
	x[0][0] = x[1][1] = 0;
	x[0][1] = x[1][0] = -INF;
}
inline void init(int x[][2], int g[])
{
	x[0][0] = x[0][1] = g[0];
	x[1][0] = g[1], x[1][1] = -INF;
}
inline void init(int p[], int u)
{
	p[0] = 0, p[1] = x[u];
}
inline void mul(int a[][2], int b[][2], int c[][2])
{
	static int t[2][2];
	t[0][0] = max(a[0][0] + b[0][0], a[0][1] + b[1][0]);
	t[0][1] = max(a[0][0] + b[0][1], a[0][1] + b[1][1]);
	t[1][0] = max(a[1][0] + b[0][0], a[1][1] + b[1][0]);
	t[1][1] = max(a[1][0] + b[0][1], a[1][1] + b[1][1]);
	c[0][0] = t[0][0];
	c[0][1] = t[0][1];
	c[1][0] = t[1][0];
	c[1][1] = t[1][1];
}
inline void mul(int a[][2], int b[], int c[])
{
	static int t[2];
	t[0] = max(a[0][0] + b[0], a[0][1] + b[1]);
	t[1] = max(a[1][0] + b[0], a[1][1] + b[1]);
	c[0] = t[0];
	c[1] = t[1];
}

void build(int &u, int a, int b, int eid)
{
	u = ++ pid;
	if(a == b) return a == eid ? init(t[u].x) : init(t[u].x, g[rnk[a]]);
	int mid = a + b >> 1;
	build(t[u].l, a, mid, eid), build(t[u].r, mid + 1, b, eid);
	mul(t[t[u].l].x, t[t[u].r].x, t[u].x);
}
void modify(int u, int x, int g[], int a, int b, int eid)
{
	if(a == b) return a == eid ? init(t[u].x) : init(t[u].x, g);
	int mid = a + b >> 1;
	if(x <= mid) modify(t[u].l, x, g, a, mid, eid);
	else modify(t[u].r, x, g, mid + 1, b, eid);
	mul(t[t[u].l].x, t[t[u].r].x, t[u].x);
}
inline void query(int u, int g[])
{
	mul(t[u].x, g, g);
}

inline void add(int a, int b)
{
	ne[ ++ idx] = la[a];
	la[a] = idx;
	en[idx] = b;
}
void dfs1(int u, int f)
{
	fa[u] = f, dep[u] = dep[f] + 1, size[u] = 1;
	for(int i = la[u]; i; i = ne[i])
	{
		int v = en[i];
		if(v != f)
		{
			dfs1(v, u);
			size[u] += size[v];
			if(size[v] > size[son[u]]) son[u] = v;
		}
	}
}
void dfs2(int u, int ft)
{
	top[u] = ft;
	rnk[id[u] = ++ dfst] = u;
	if(son[u])
	{
		dfs2(son[u], ft), End[u] = End[son[u]];
		g[u][0] = 0, g[u][1] = x[u];
		for(int i = la[u]; i; i = ne[i])
		{
			int v = en[i];
			if(v != fa[u] && v != son[u])
			{
				dfs2(v, v);
				g[u][0] += max(f[v][0], f[v][1]);
				g[u][1] += f[v][0];
			}
		}
		f[u][0] = g[u][0] + max(f[son[u]][0], f[son[u]][1]);
		f[u][1] = g[u][1] + f[son[u]][0];
	}
	else End[u] = u, g[u][1] = f[u][1] = x[u];
	if(u == ft) build(root[u], id[u], id[End[u]], id[End[u]]);
}

inline int modify(int u, int y)
{
	static int p[2][2], f1[2], f2[2];
	g[u][1] += y - x[u];
	init(p, g[u]);
	int t = 1;
	while(top[u] != 1)
	{
		int v = top[u], w = fa[v];
		init(f1, End[u]);
		query(root[v], f1);
		if(t) x[u] = y, t = 0;
		modify(root[v], id[u], g[u], id[v], id[End[v]], id[End[v]]);
		init(f2, End[u]);
		query(root[v], f2);
		g[w][0] += max(f2[0], f2[1]) - max(f1[0], f1[1]);
		g[w][1] += f2[0] - f1[0];
		u = w;
	}
	if(t) x[u] = y;
	modify(root[1], id[u], g[u], id[1], id[End[1]], id[End[1]]);
	init(f1, End[1]);
	query(root[1], f1);
	return max(f1[0], f1[1]);
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &x[i]);
	for(int i = 1; i < n; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	dfs1(1, 0), dfs2(1, 1);
	int ans = 0;
	while(m -- )
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x ^= ans;
		printf("%d\n", ans = modify(x, y));
	}
	return 0;
}