洛谷P4719 【模板】动态dp(ddp LCT)

题意

题目链接

Sol

动态dp板子题。有些细节还没搞懂，待我研究明白后再补题解。。。

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int MAXN = 1e5 + 10, INF = INT_MAX;

template<typename A, typename B> inline bool chmax(A &x, B y) {

	return x < y ? x = y, 1 : 0;

}

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, a[MAXN], f[MAXN][2];

struct Ma {

	LL m[3][3];

	Ma() {

		memset(m, -0x3f, sizeof(m));

	}

	Ma operator * (const Ma &rhs) const {

		Ma ans;

		for(int i = 1; i <= 2; i++)

			for(int j = 1; j <= 2; j++)

				for(int k = 1; k <= 2; k++)

					chmax(ans.m[i][j], m[i][k] + rhs.m[k][j]);

		return ans;

	}

}val[MAXN], sum[MAXN];

vector<int> v[MAXN];

int ch[MAXN][2], fa[MAXN];

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

void update(int k) {

	sum[k] = val[k];

	if(rs(k)) sum[k] = sum[k] * sum[rs(k)];

	if(ls(k)) sum[k] = sum[ls(k)] * sum[k];

}

bool ident(int x) {

	return rs(fa[x]) == x;

}

bool isroot(int x) {

	return ls(fa[x]) != x && rs(fa[x]) != x;

}

void connect(int x, int _fa, int tag) {

	fa[x] = _fa;

	ch[_fa][tag] = x;

}

void rotate(int x) {

	int y = fa[x], r = fa[y], yson = ident(x), rson = ident(y);

	int b = ch[x][yson ^ 1];

	fa[x] = r;

	if(!isroot(y)) connect(x, r, rson);

	connect(b, y, yson);

	connect(y, x, yson ^ 1);

	update(y); update(x);

}

void splay(int x) {

	for(int y = fa[x]; !isroot(x); rotate(x), y = fa[x])

		if(!isroot(y))

			rotate(ident(y) == ident(x) ? y : x);

}

void access(int x) {

	for(int y = 0; x; x = fa[y = x]) {

		splay(x);

		if(rs(x)) {

			val[x].m[1][1] += max(sum[rs(x)].m[1][1], sum[rs(x)].m[2][1]);

			val[x].m[2][1] += sum[rs(x)].m[1][1];

		}

		if(y) {

			val[x].m[1][1] -= max(sum[y].m[1][1], sum[y].m[2][1]);

			val[x].m[2][1] -= sum[y].m[1][1];

		}

		val[x].m[1][2] = val[x].m[1][1];

		rs(x) = y;

		update(x);

	}

}

int Modify(int p, int v) {

	access(p); splay(p);

	val[p].m[2][1] -= a[p] - v;

	update(p);

	a[p] = v;

	splay(1);

	return max(sum[1].m[1][1], sum[1].m[2][1]);

}

void dfs(int x, int _fa) {

	fa[x] = _fa;

	f[x][1] = a[x];

	for(auto &to : v[x]) {

		if(to == _fa) continue;

		dfs(to, x);

		f[x][0] += max(f[to][0], f[to][1]);

		f[x][1] += f[to][0];

	}

	val[x].m[1][1] = f[x][0]; val[x].m[1][2] = f[x][0];

	val[x].m[2][1] = f[x][1]; val[x].m[2][2] = -INF;

	update(x);

//	sum[x] = val[x];

}

int main() {

	//freopen("a.in", "r", stdin);

	N = read(); M = read();

	for(int i = 1; i <= N; i++) a[i] = read();

	for(int i = 1; i < N; i++) {

		int x = read(), y = read();

		v[x].push_back(y);

		v[y].push_back(x);

	}

	dfs(1, 0);

	while(M--) {

		int x = read(), y = read();

		printf("%d\n", Modify(x, y));

	}

	return 0;

}