一开始 MAXN 开到 1e7 ， RE on #2,#3 ， 开到 1.7e7也是

然后开到 2e7 的时候 MLE on #2 #3

这玩意空间有什么讲究吗？还是我哪里开小了？

#include<cstdio>
#include<cctype>
#include<algorithm>
#define R register
#define INF (0x3f3f3f3f)
using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
#define getchar() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	R int x = 0; bool f = false; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = true; c = getchar();}
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return (f ? -x : x);
}
inline void write(R int x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}

const int MAXN = 1000005;

int n, Q, a[MAXN];
int dp[MAXN][2], ldp[MAXN][2];
struct edge {
	int to, nex;
}e[MAXN << 1]; int idx, head[MAXN];
inline void add(R int u, R int v) {
	e[++ idx].to = v;
	e[idx].nex = head[u];
	head[u] = idx;
}

struct Matrix {
	int n, m, d[3][3];
	inline Matrix(R int x = 2, R int y = 2) {
		n = x, m = y;
		for (R int i = 0; i < 3; ++ i)
			for (R int j = 0; j < 3; ++ j)
				d[i][j] = -INF;
	}
	inline Matrix operator * (const Matrix &B) {
		Matrix C(n, B.m); 
		for (R int i = 1; i <= n; ++ i)
			for (R int k = 1; k <= m; ++ k)
				for (R int j = 1; j <= B.m; ++ j)
					C.d[i][j] = max(C.d[i][j], d[i][k] + B.d[k][j]);
		return C;
	} 
}val[MAXN];
inline Matrix Unit(int n = 2) {
	Matrix A(n, n);
	for (int i = 1; i <= n; ++ i)
		A.d[i][i] = 0;
	return A; 
}
inline void Init(R int x) {
	val[x].d[2][1] = ldp[x][1];
	val[x].d[1][1] = val[x].d[1][2] = ldp[x][0];
}

int stc[MAXN], top, sm[MAXN];
int rt;
namespace LCT {
	Matrix tr[MAXN];
	int fa[MAXN], lc[MAXN], rc[MAXN];
	inline int Build(int l, int r) {
		if (l > r) return 0; if (l == r) return stc[l];
		int x = (sm[r] - sm[l - 1]) / 2 + sm[l - 1];
		int mid = lower_bound(sm + l, sm + r, x) - sm;
		fa[lc[stc[mid]] = Build(l, mid - 1)] = stc[mid];
		fa[rc[stc[mid]] = Build(mid + 1, r)] = stc[mid];
		return stc[mid];
	}
	inline bool Isrt(int x) {
		return lc[fa[x]] != x && rc[fa[x]] != x;
	} 
	inline void push_up(int u) {
		tr[u] = tr[lc[u]] * val[u] * tr[rc[u]];
	}
	inline void dfs(int u) {
		if (!u) return;
		if (!fa[u]) rt = u;
		dfs(lc[u]), dfs(rc[u]);
		push_up(u); 
	}
	inline void Prew() {
		tr[0] = Unit();
		for (int i = 1; i <= n; ++ i)
			Init(i); 
		for (int i = 1; i <= n; ++ i)
			if (Isrt(i)) dfs(i);
	}
	inline void Modify(int u, int w) {
		val[u].d[2][1] += w - a[u]; a[u] = w;
		int nw; Matrix lst, now;
		for (nw = u; nw; nw = fa[nw]) 
			if (Isrt(nw) && fa[nw]) {
				u = fa[nw];
				lst = tr[nw], push_up(nw), now = tr[nw];
				val[u].d[1][1] += max(now.d[1][1], now.d[2][1]) - max(lst.d[1][1], lst.d[2][1]);
				val[u].d[1][2] = val[u].d[1][1];
				val[u].d[2][1] += now.d[1][1] - lst.d[1][1];
			} else push_up(nw);
	}
}

namespace Tree {
	int fa[MAXN];
	int siz[MAXN], wson[MAXN];
	inline void dfs1(R int u) {
		siz[u] = 1;
		for (R int i = head[u]; i; i = e[i].nex) {
			R int v = e[i].to;
			if (v == fa[u]) continue;
			fa[v] = u; dfs1(v);
			siz[u] += siz[v];
			if (siz[v] > siz[wson[u]]) wson[u] = v;
		}
	}
	inline void dfs2(R int u) {
		dp[u][1] = ldp[u][1] = a[u];
		if (!wson[u]) {
			if (wson[fa[u]] != u) {
				top = 0;
				for (int v = u; v; v = wson[v])
					stc[++ top] = v, sm[top] = sm[top - 1] + siz[v] - siz[wson[u]];
				LCT::fa[LCT::Build(1, top)] = fa[u];
			}
			return;
		}
		dfs2(wson[u]); dp[u][1] += dp[wson[u]][0];
		dp[u][0] += max(dp[wson[u]][0], dp[wson[u]][1]);
		for (R int i = head[u]; i; i = e[i].nex) {
			R int v = e[i].to;
			if (v == fa[u] || v == wson[u]) continue; dfs2(v);
			dp[u][0] += max(dp[v][0], dp[v][1]);
			ldp[u][0] += max(dp[v][0], dp[v][1]);
			dp[u][1] += dp[v][0], ldp[u][1] += dp[v][0];
		}
		if (wson[fa[u]] != u) {
			top = 0; 
			for (int v = u; v; v = wson[v])
				stc[++ top] = v, sm[top] = sm[top - 1] + siz[v] - siz[wson[u]];
			LCT::fa[LCT::Build(1, top)] = fa[u];
		}
	}
}

int main()
{
	n = read(), Q = read();
	for (R int i = 1; i <= n; ++ i) a[i] = read();
	for (R int i = 1; i < n; ++ i) {
		R int u = read(), v = read();
		add(u, v); add(v, u);
	}
	Tree::dfs1(1); Tree::dfs2(1); LCT::Prew();
	int x, y, lst = 0;
	while (Q --) {
		x = read(), y = read(); x ^= lst;
		LCT::Modify(x, y);
		write(lst = max(LCT::tr[1].d[1][1], LCT::tr[1].d[2][1]));
		putchar('\n');
	}
	return 0;
}