? 解题记录 ? ? 模板 ? ? 动态规划 ? ? 树链剖分 ?    2018-12-10 11:15:59    632    0    0

## 输入输出样例

10 10
-11 80 -99 -76 56 38 92 -51 -34 47
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93

186
186
190
145
189
288
244
320
258
304

## 说明

#include<cstdio>
#include<algorithm>
#include<cstring>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
int v, next;
} e[maxn << 1];
int head[maxn], cnt, n, m, u, v, w[maxn], MXR[maxn];
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
}
struct MAT {int d[2][2];};
MAT tmp;
MAT operator * (const MAT & A, const MAT & B) {
tmp = (MAT){-inf, -inf, -inf, -inf};
For(i, 0, 1) For(j, 0, 1) For(k, 0, 1)
tmp.d[i][j] = max(A.d[k][j] + B.d[i][k], tmp.d[i][j]);
return tmp;
}

int siz[maxn], fa[maxn], top[maxn], son[maxn], d[maxn];
int dfn[maxn], org[maxn], dcnt, dp[maxn][2], ldp[maxn][2];
void dfs1(int u, int p) {
siz[u] = 1;
fa[u] = p, d[u] = d[p] + 1;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
dfs1(v, u), siz[u] += siz[v];
if(!son[u] || siz[son[u]] < siz[v])
son[u] = v;
}
}

void work(int u) {
ldp[u][1] = dp[u][1] = w[u];
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa[u]) continue;
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa[u] || v == son[u]) continue;
ldp[u][0] += max(dp[v][0], dp[v][1]);
ldp[u][1] += dp[v][0];
}
}

int dfs2(int u, int tp) {
dfn[u] = ++dcnt;
org[dfn[u]] = u;
top[u] = tp, MXR[u] = u;
if(son[u]) MXR[u] = dfs2(son[u], tp);
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
work(u);
return MXR[u];
}

namespace SGT {
MAT t[maxn << 2];
void push_up(int rt) {
t[rt] = t[rt << 1 | 1] * t[rt << 1];
}
void build(int l, int r, int rt) {
if(l == r) {
t[rt] = (MAT) {ldp[org[l]][0], ldp[org[l]][0],
ldp[org[l]][1], -inf};
rt;
return ;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
void edit(int x, int tl, int tr, const MAT &nw, int rt) {
if(tl == tr) {
t[rt] = nw;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid) edit(x, tl, mid, nw, rt << 1);
else edit(x, mid + 1, tr, nw, rt << 1 | 1);
push_up(rt);
}
MAT query(int l, int r, int tl, int tr, int rt) {
if(l == tl && r == tr) return t[rt];
int mid = tl + tr >> 1;
if(r <= mid) return query(l, r, tl, mid, rt << 1);
else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
else return query(mid + 1, r, mid + 1, tr, rt << 1 | 1) *
query(l, mid, tl, mid, rt << 1);
}
}

int Q() {
MAT ans = SGT::query(1, dfn[MXR[1]], 1, n, 1);
return max(ans.d[0][0], ans.d[1][0]);
}

void Ref(int x, int dp0, int dp1) {
ldp[fa[x]][0] -= max(dp[x][0], dp[x][1]);
ldp[fa[x]][1] -= dp[x][0];
dp[x][0] = dp0, dp[x][1] = dp1;
ldp[fa[x]][0] += max(dp[x][0], dp[x][1]);
ldp[fa[x]][1] += dp[x][0];
}

void E(int x, int W) {
ldp[x][1] -= w[x];
ldp[x][1] += (w[x] = W);
while(x) {
SGT::edit(dfn[x], 1, n, (MAT) {ldp[x][0], ldp[x][0],
ldp[x][1], -inf}, 1);
x = top[x];
tmp = SGT::query(dfn[x], dfn[MXR[x]], 1, n, 1);
Ref(x, tmp.d[0][0], tmp.d[1][0]);
x = fa[x];
}
}

int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
for(register int i = 1; i < n; ++i)
scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
dfs1(1, 0), dfs2(1, 1), SGT::build(1, n, 1);
//printf("%d\n", Q());
for(register int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
E(u, v);
printf("%d\n", Q());
}
return 0;
}

632 人读过

0 条评论