11/13
09:36
OI

[NOIP2018]保卫王国 [动态DP]

保卫王国

因为luogu上DDP板子是独立集所以就写了这个版本

我们可以发现这题要求的是最小覆盖,最小覆盖=全集-最大独立集,我们可以考虑求独立集

可以写一个naive的暴力DP,令f_{x,0/1}分别表示x,选或不选

f_{x,0} = \sum \max f_{y,0}, f_{y,1}

f_{x,1} = A_x + \sum f_{y,0}

记录g_{x,0/1},维护轻儿子的信息 记yx的重儿子,这样定义g:

f_{x,0} = g_{x,0} + \max f_{y,0}, f_{y,1}

f_{x,1} = g_{x,1} + f_{y,0}

然后改写一下

f_{x,0} = \max \lbrace g_{x,0} + f_{y,0}, g_{x,0} + f_{y,1} \rbrace

f_{x,1} = \max \lbrace g_{x,1} + f_{y,0}, -\infty \rbrace

我们重载矩阵的乘法操作,定义如下

C_{i,j} = \max A_{i,k} + B_{k,j}

这样的矩阵乘法依然有好的性质: 满足结合率

所以可以用矩阵维护DP. 链剖,然后一条链上用线段树维护矩阵. 转移是从下往上的,然而线段树方向相反,所以转移矩阵在前,要写成这样

\begin{bmatrix} g_{x,0} & g_{x,0} \\ g_{x,1} & -\infty \end{bmatrix} \begin{bmatrix} f_{y,0} \\ f_{y,1} \end{bmatrix}= \begin{bmatrix} f_{x,0} \\ f_{x,1} \end{bmatrix}

然后就可以做了

一些细节:一个点的值,是它在的链底到它乘积. 计算的时候要用到链底,所以要记录. 跳链的时候记录旧值新值,以计算新贡献

重链剖分O(nlog^2n) 如果用LCT是O(nlogn),不过跑得更慢

回到本题,强制选和不选可以用赋值为正负无穷解决,然后套板子就行


当然实际上这个题也可以倍增. 大概思路就是我们发现钦定a,b状态之后,发现答案分成三部分: a,b的子树,二者之间的链,lca到根.

然后考虑倍增,f_{x,i,j,k}表示x跳了2^i次,两端点状态为j,k.合并两端的时候,枚举中间点的状态取最优,大力分类讨论即可O(nlogn)

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e5 + 233;
typedef long long ll;
const ll INF = 1e15;

int n, m, A[N];
std::vector<int> G[N];
int fa[N], son[N], top[N], size[N], dep[N],
  dfn[N], id[N], num, end[N];
ll sum, f[N][2];

struct Matrix {
  ll mat[2][2];
  Matrix() {
    memset(mat, 0xcf, sizeof(mat));
  }
  inline ll* operator[](int x) {
    return mat[x];
  }
  inline Matrix operator*(Matrix y) {
    Matrix ret;
    for (int i = 0; i < 2; ++i)
      for (int k = 0; k < 2; ++k)
        for (int j = 0; j < 2; ++j)
          ret.mat[i][j] = std::max(ret.mat[i][j], mat[i][k] + y[k][j]);
    return ret;
  }
};
Matrix g[N];

struct Segment_Tree {
  #define ls(p) p << 1
  #define rs(p) p << 1 | 1
  Matrix mat[N * 4];

  inline void pushup(int p) {
    mat[p] = mat[ls(p)] * mat[rs(p)];
  }

  void build(int p, int l, int r) {
    if (l == r)
      return (void)(mat[p] = g[id[l]]);
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
  }

  void change(int p, int x, int L, int R) {
    if (L == R)
      return (void)(mat[p] = g[id[x]]);
    int mid = (L + R) >> 1;
    if (x <= mid)
      change(ls(p), x, L, mid);
    else
      change(rs(p), x, mid + 1, R);
    pushup(p);
  }

  Matrix query(int p, int l, int r, int L, int R) {
    if (l <= L && r >= R)
      return mat[p];
    int mid = (L + R) >> 1;
    if (l <= mid && r > mid)
      return query(ls(p), l, r, L, mid)
        * query(rs(p), l, r, mid + 1, R);
    else if (l <= mid)
      return query(ls(p), l, r, L, mid);
    else
      return query(rs(p), l, r, mid + 1, R);
  }
} tree;

void dfs1(int x) {
  size[x] = 1; dep[x] = dep[fa[x]] + 1;
  for (int y : G[x]) if (y != fa[x]) {
    fa[y] = x; dfs1(y);
    if (size[y] > size[son[x]])
      son[x] = y;
    size[x] += size[y];
  }
}

void dfs2(int x, int topf) {
  top[x] = topf; dfn[x] = ++num;
  id[num] = x; end[topf] = x;

  f[x][0] = 0, f[x][1] = A[x];
  g[x][0][0] = g[x][0][1] = 0;
  g[x][1][0] = A[x];

  if (!son[x])
    return;
  dfs2(son[x], topf);

  f[x][0] += std::max(f[son[x]][0], f[son[x]][1]);
  f[x][1] += f[son[x]][0];

  for (int y : G[x])
    if (y != fa[x] && y != son[x]) {
      dfs2(y, y);
      f[x][0] += std::max(f[y][0], f[y][1]);
      f[x][1] += f[y][0];
      g[x][0][0] += std::max(f[y][0], f[y][1]);
      g[x][0][1] = g[x][0][0];
      g[x][1][0] += f[y][0];
    }
}

inline void update(int x, ll y) {
  g[x][1][0] += y - A[x];
  A[x] = y;

  Matrix pre, nxt;
  while (x) {
    pre = tree.query(1, dfn[top[x]], dfn[end[top[x]]], 1, n);
    tree.change(1, dfn[x], 1, n);
    nxt = tree.query(1, dfn[top[x]], dfn[end[top[x]]], 1, n);
    x = fa[top[x]];

    g[x][0][0] += std::max(nxt[0][0], nxt[1][0]) - std::max(pre[0][0], pre[1][0]);
    g[x][0][1] = g[x][0][0];
    g[x][1][0] += nxt[0][0] - pre[0][0];
  }
}

int main() {
  n = rd(), m = rd();
  { char op[5]; scanf("%s", op); }
  for (int i = 1; i <= n; ++i)
    sum += (A[i] = rd());
  for (int i = 1; i < n; ++i) {
    int x = rd(), y = rd();
    G[x].push_back(y);
    G[y].push_back(x);
  }

  dfs1(1);
  dfs2(1, 1);
  tree.build(1, 1, n);

  while (m--) {
    int a = rd(), x = rd(), b = rd(), y = rd();
    if (!x && !y && (fa[a] == b || fa[b] == a)) {
      puts("-1"); continue;
    }
    ll tmp_a = A[a], tmp_b = A[b];
    ll new_a = !x ? INF : -INF,
      new_b = !y ? INF : -INF;
    update(a, new_a);
    update(b, new_b);
    Matrix ans = tree.query(1, dfn[1], dfn[end[1]], 1, n);
    ll tmp = sum - tmp_a - tmp_b;
    tmp += std::max(new_a, tmp_a) + std::max(new_b, tmp_b);
    printf("%lld\n", tmp - std::max(ans[0][0], ans[1][0]));
    update(a, tmp_a);
    update(b, tmp_b);
  }
  return 0;
}