2018-12-28 16:22:01

### 引例：最大子段和问题

$$f_i=\max\{f_{i-1}+a_i,a_i\}$$

$$g_i=\max\{g_{i-1},f_i\}$$

g[0] = -inf;
for (int i = 1; i <= n; ++i) {
f[i] = max(f[i - 1] + a[i], a[i]);
g[i] = max(g[i - 1], f[i]);
}
printf("%d\n", g[n]);

### 矩阵乘法

$$\begin{bmatrix}3&4&7&5&6&3&-2\\1&0&0&0&0&0&0\\0&0&2&0&0&0&0\\0&0&0&1&3&3&1\\0&0&0&0&1&2&1\\0&0&0&0&0&1&1\\0&0&0&0&0&0&1\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\\2^n\\n^3\\n^2\\n\\1\end{bmatrix}=\begin{bmatrix}f_n\\f_{n-1}\\2^{n+1}\\(n+1)^3\\(n+1)^2\\n+1\\1\end{bmatrix}$$

### 求区间最大子段和

$$f_i=\max\{f_{i-1}+a_i,a_i\}$$

$$g_i=\max\{g_{i-1},f_i\}$$

#### 广义的矩阵乘法

$$a\times(b+c)=a\times b+a\times c$$

$$(ABC)_{i,j}=\sum\limits_{k=1}^p (AB)_{i,k}C_{k,j}$$

$$=\sum\limits_{k=1}^p C_{k,j}\sum\limits_{t=1}^m A_{i,t}B_{t,k}$$

$$=\sum\limits_{t=1}^m A_{i,t}\sum\limits_{k=1}^pB_{t,k}C_{k,j}$$

$$=(A(BC))_{i,j}$$

$$a+\max\{b,c\}=\max\{a+b,a+c\}$$

$$a+\min\{b,c\}=\min\{a+b,a+c\}$$

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>

template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
}
template <typename T> void write(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) {
write(x); puts("");
}
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, 1) : 0; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, 1) : 0; }

typedef long long LL;

const int maxn = 1e5 + 207;
const LL inf = 1e10;

int v[maxn << 1], head[maxn], next[maxn << 1], tot;
LL f[maxn][2], g[maxn][2], h[maxn][30][2][2], val[maxn];
int fa[maxn][30], dep[maxn];
int n, m;

inline void ae(int x, int y) {
}
void dfs1(int x) {
using std::min;
f[x][1] = val[x]; dep[x] = dep[fa[x][0]] + 1;
for (int i = 1; i <= 20; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = head[x]; i; i = next[i])
if (v[i] != fa[x][0]) {
fa[v[i]][0] = x;
dfs1(v[i]);
f[x][0] += f[v[i]][1];
f[x][1] += min(f[v[i]][0], f[v[i]][1]);
}
}
void dfs2(int x) {
using std::min;
for (int i = 1; i <= 20; ++i)
for (int j = 0; j <= 1; ++j)
for (int k = 0; k <= 1; ++k)
h[x][i][j][k] = min(h[x][i - 1][j][0] + h[fa[x][i - 1]][i - 1][0][k],
h[x][i - 1][j][1] + h[fa[x][i - 1]][i - 1][1][k]);
for (int i = head[x]; i; i = next[i])
if (v[i] != fa[x][0]) {
h[v[i]][0][0][0] = inf;
h[v[i]][0][0][1] = f[x][1] - min(f[v[i]][0], f[v[i]][1]);
h[v[i]][0][1][0] = f[x][0] - f[v[i]][1];
h[v[i]][0][1][1] = f[x][1] - min(f[v[i]][0], f[v[i]][1]);
g[v[i]][0] = g[x][1] + f[x][1] - min(f[v[i]][0], f[v[i]][1]);
g[v[i]][1] = min(g[v[i]][0], g[x][0] + f[x][0] - f[v[i]][1]);
dfs2(v[i]);
}
}

inline bool isAncestor(int x, int y) {
for (int i = 20; ~i; --i) if (dep[fa[y][i]] >= dep[x]) y = fa[y][i];
return x == y;
}
inline LL getAns(int x, int qx, int y, int qy) {
using std::min;
using std::swap;
if (dep[x] < dep[y]) { swap(x, y); swap(qx, qy); }
if (isAncestor(y, x)) {
LL tmp[2] = {f[x][0], f[x][1]}; tmp[qx ^ 1] = inf;
for (int i = 20; ~i; --i) if (dep[fa[x][i]] > dep[y]) {
LL t0 = min(tmp[0] + h[x][i][0][0], tmp[1] + h[x][i][1][0]);
LL t1 = min(tmp[0] + h[x][i][0][1], tmp[1] + h[x][i][1][1]);
tmp[0] = t0; tmp[1] = t1; x = fa[x][i];
}
LL ans = min(tmp[0] + h[x][0][0][qy], tmp[1] + h[x][0][1][qy]) + g[y][qy];
return ans < inf ? ans : -1;
} else {
LL tx[2] = {f[x][0], f[x][1]}; tx[qx ^ 1] = inf;
LL ty[2] = {f[y][0], f[y][1]}; ty[qy ^ 1] = inf;
for (int i = 20; ~i; --i) if (dep[fa[x][i]] >= dep[y]) {
LL t0 = min(tx[0] + h[x][i][0][0], tx[1] + h[x][i][1][0]);
LL t1 = min(tx[0] + h[x][i][0][1], tx[1] + h[x][i][1][1]);
tx[0] = t0; tx[1] = t1; x = fa[x][i];
}
for (int i = 20; ~i; --i) if (fa[x][i] != fa[y][i]) {
LL t0 = min(tx[0] + h[x][i][0][0], tx[1] + h[x][i][1][0]);
LL t1 = min(tx[0] + h[x][i][0][1], tx[1] + h[x][i][1][1]);
tx[0] = t0; tx[1] = t1; x = fa[x][i];
t0 = min(ty[0] + h[y][i][0][0], ty[1] + h[y][i][1][0]);
t1 = min(ty[0] + h[y][i][0][1], ty[1] + h[y][i][1][1]);
ty[0] = t0; ty[1] = t1; y = fa[y][i];
}
LL ans = min(f[fa[x][0]][0] - f[y][1] - f[x][1] + tx[1] + ty[1] + g[fa[x][0]][0],
f[fa[x][0]][1] - min(f[x][0], f[x][1]) - min(f[y][0], f[y][1])
+ min(tx[0], tx[1]) + min(ty[0], ty[1]) + g[fa[x][0]][1]);
return ans < inf ? ans : -1;
}
}

int main() {
{ char xysILoveYou[10]; scanf("%s", xysILoveYou); }
for (int i = 1; i <= n; ++i) read(val[i]);
for (int i = 1; i != n; ++i) {
ae(x, y);
}
dfs1(1);
dfs2(1);
while (m--) {
int x, qx, y, qy;
}