$$f _ {x, 0} = \sum _ y \max(f _ {y, 0}, f _ {y, 1})$$
$$f _ {x, 1} = v _ x + \sum _ y f _ {y, 0}$$

$$f _ {x, 0} = \max(f _ {h, 0}, f _ {h, 1}) + \sum _ z \max(f _ {z, 0}, f _ {z, 1})$$
$$f _ {x, 1} = v _ x + f _ {h, 0} + \sum _ z f _ {z, 0}$$

$$f _ {x, 0} = \max(f _ {h, 0}, f _ {h, 1}) + g _ {x, 0}$$
$$f _ {x, 1} = f _ {h, 0} + g _ {x, 1}$$

$$A \times B = C$$
$$C _ {i, j} = \max _ k (A _ {i, k} + B _ {k, j})$$

$$\left[ \begin{matrix} g _ {x, 0} & g _ {x, 1} \\ g _ {x, 0} & -\infty \end{matrix} \right]$$

$$\left[ \begin{matrix}f _ {h, 0} & f _ {h, 1}\end{matrix} \right] \times \left[ \begin{matrix} g _ {x, 0} & g _ {x, 1} \\ g _ {x, 0} & -\infty \end{matrix} \right] = \left[ \begin{matrix}f _ {x, 0} & f _ {x, 1}\end{matrix} \right]$$

（下面这个代码是卡了常的，能过加强版，需要加个强制在线和开大数据范围）

（加强版其实意义不大，整个就是无聊卡长，弄得我还写了人生第一份 fread 读入优化）

#include <bits/stdc++.h>

#define NS (100005)
#define INF (1000000000)

using namespace std;

inline char getC()
{
static char buff[100000], *p = buff, *q = buff;
if (p == q)
{
q = (p = buff) + fread(buff, 1, 100000, stdin);
if (p == q) return EOF;
}
return *p++;
}

template<typename _Tp> inline void IN(_Tp &dig)
{
char c; bool flag = 0; dig = 0;
while (c = getC(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getC();
if (flag) dig = -dig;
}

inline int Max(int a, int b) { return a > b ? a : b; }

int n, m, V[NS], hs[NS], sz[NS];

struct graph
{
int head[NS], nxt[NS << 1], to[NS << 1], sz;
void push(int a, int b)
{
}
} g;

struct M
{
int d[2][2];
int (& operator [] (const int a))[2] { return d[a]; }
inline int mx()
{
return Max(Max(d[0][0], d[0][1]), Max(d[1][0], d[1][1]));
}
void operator *= (M &oth)
{
static int tmp[2][2];
tmp[0][0] = Max(d[0][0] + oth[0][0], d[0][1] + oth[1][0]);
tmp[0][1] = Max(d[0][0] + oth[0][1], d[0][1] + oth[1][1]);
tmp[1][0] = Max(d[1][0] + oth[0][0], d[1][1] + oth[1][0]);
tmp[1][1] = Max(d[1][0] + oth[0][1], d[1][1] + oth[1][1]);
memmove(d, tmp, sizeof(d));
}
};

int root, A[NS];

struct N { int f, s[2]; M d, m; } e[NS];

inline bool isrt(int a)
{
return (e[e[a].f].s[0] != a) && (e[e[a].f].s[1] != a);
}

void dfs(int a, int fa)
{
sz[a] = 1, e[a].d[0][1] = V[a], e[a].d[1][1] = -INF;
for (int i = g.head[a], mx = 0; ~i; i = g.nxt[i])
if (g[i] != fa)
{
dfs(g[i], a), sz[a] += sz[g[i]];
if (sz[g[i]] > mx) mx = sz[g[i]], hs[a] = g[i];
}
}

inline void pup(int a)
{
e[a].m = e[e[a].s[1]].m;
e[a].m *= e[a].d;
if (e[a].s[0]) e[a].m *= e[e[a].s[0]].m;
}

inline void pupd(int a, int b, bool f)
{
if (f)
{
e[a].d[0][0] += e[b].m.mx(), e[a].d[1][0] = e[a].d[0][0];
e[a].d[0][1] += Max(e[b].m[0][0], e[b].m[1][0]);
}
else
{
e[a].d[0][0] -= e[b].m.mx(), e[a].d[1][0] = e[a].d[0][0];
e[a].d[0][1] -= Max(e[b].m[0][0], e[b].m[1][0]);
}
}

int build(int l, int r)
{
if (l > r) return 0;
int sum = 0, tot = sz[A[l]], mid = l;
for (int i = l; i <= r; i += 1) sum += sz[A[i]];
while ((tot << 1) <= sum) mid++, tot += sz[A[mid]];
int a = A[mid];
e[a].s[0] = build(l, mid - 1), e[a].s[1] = build(mid + 1, r);
if (e[a].s[0]) e[e[a].s[0]].f = a;
if (e[a].s[1]) e[e[a].s[1]].f = a;
pup(a);
return a;
}

bool book[NS];

int constract(int a)
{
for (int i = a; i; i = hs[i]) book[i] = 1;
for (int i = a; i; i = hs[i])
for (int j = g.head[i]; ~j; j = g.nxt[j])
if (!book[g[j]])
{
int k = constract(g[j]);
e[k].f = i, pupd(i, k, 1);
}
A[0] = 0;
for (int i = a; i; i = hs[i]) A[++A[0]] = i;
for (int i = 1; i < A[0]; i += 1) sz[A[i]] -= sz[A[i + 1]];
return build(1, A[0]);
}

void modify(int a, int k)
{
e[a].d[0][1] += k - V[a], V[a] = k;
while (a)
{
if (e[a].f && isrt(a))
pupd(e[a].f, a, 0), pup(a), pupd(e[a].f, a, 1);
else pup(a);
a = e[a].f;
}
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), e[0].m[0][1] = e[0].m[1][0] = -INF, e[0].d = e[0].m;
for (int i = 1; i <= n; i += 1) IN(V[i]);
for (int i = 1, a, b; i < n; i += 1)
IN(a), IN(b), g.push(a, b), g.push(b, a);
dfs(1, 0), root = constract(1);
for (int i = 1, x, y; i <= m; i += 1)
{
IN(x), IN(y), modify(x, y);
printf("%d\n", e[root].m.mx());
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 2 条评论

#### Remmina · 2019年3月13日 4:18 下午

其实不止是代码风格问题，他建树还是反着建的（左儿子大右儿子小），然后 push_up 的时候让矩阵反着乘。。。真的是。。。奇妙