题意
题目链接
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("%dn", modify(x, y)); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605083.html