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}$,维护轻儿子的信息 记$y$为$x$的重儿子,这样定义$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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#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;
}