题目链接

LuoguP4719

题目概括

给定一棵带点权的树,问这棵树的最大点权独立集。
问题要求动态点权修改

思路要点

现代科技:动态DP(DDP)暴露了我矩阵乘法不合格的事实
不带修改的就是一个简单的树形$DP$。
定义$f[i][0/1]$表示$i$为根节点的子树,根节点选择还是不选的最大点权独立集。
$$f[i][0] = \sum Max\{ f[j][0],f[j][1]\}$$
$$f[i][1] = value[i] + \sum f[j][0]$$

问题弱化$1$

考虑如果这是一条链(问题依旧带修改),那么答案之和前一项有关。
转移方程就变成了,其中的$i - 1$是广义上的$i - 1$。
$$f[i][0] = Max\{ f[i - 1][0], f[i - 1][1]\}$$
$$f[i][1] = a[i] + f[i - 1][0]$$
这个时候我们就需要对矩阵乘法进行魔改,将其转化为广义矩阵乘法。

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    for (int k = 0; k < n; k++) {
      c[i][j] = max(c[i][j], a[i][k] + a[k][j])
    }
  }
}

原题

因为线段树只能维护一条重链上的信息,所以我们需要把重儿子和轻儿子的信息分开来处理。
我们定义$g[i][0/1]$(定义不明,功能只是辅助转移)
$$g[i][0]=\sum_{j\in lightSon_i}Max\{ f[j][0], f[j][1] \}$$
$$g[i][1] = value[i] + \sum_{j\in lightSon_i} f[i][0]$$
这样就成功把重儿子和轻儿子区分开了,而且固定了方程的项数。
然后推导矩阵。(这里就不推导了)
至于在修改的时候,我们考虑这样一个做法,$x$节点先修改好自己的矩阵,然后跳到链顶,更新链顶的父亲的矩阵。

时间复杂度:$\mathcal O(nlog^2n)$

代码

#include <bits/stdc++.h>
#define inf (0x3f3f3f3f)

using namespace std;

template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T>
void writeln(T x) {
  write(x), puts("");
}

const int N = 1e5 + 5;

struct Edge {
  int to, nt;
} E[N << 1];

struct Matrix {
  int a[2][2];
  
  int* operator [](int i) {
    return a[i];
  }
  
  Matrix() {
    memset(a, 0, sizeof a);
  }
  
  Matrix(int A, int B, int C, int D) {
    a[0][0] = A, a[0][1] = B;
    a[1][0] = C, a[1][1] = D;
  }
  
  friend Matrix operator * (Matrix a, Matrix b) {
    Matrix res;
    for (int i = 0; i <= 1; i++) {
      for (int j = 0; j <= 1; j++) {
        for (int k = 0; k <= 1; k++) {
          res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
        }
      }
    }
    return res;
  }
  
  friend ostream& operator << (ostream& out, Matrix a) {
    out << "Matrix" << '\n';
    out << "======" << '\n';
    for (int i = 0; i <= 1; i++) {
      for (int j = 0; j <= 1; j++) {
        out << a[i][j] << ' ';
      }
      cout << '\n';
    }
    cout << "======" << '\n';
    return out;
  }
};

int n, m, edgeCnt = 1, dfc = 0;
int value[N], H[N], top[N], siz[N], dep[N], fa[N], son[N], dfn[N], bck[N], bot[N];
int f[N][2], g[N][2];

void addEdge(int u, int v) {
  E[++edgeCnt] = (Edge){v, H[u]};
  H[u] = edgeCnt;
}

void dfs1(int u, int ft) {
  dep[u] = dep[ft] + 1;
  fa[u] = ft;
  son[u] = 0;
  siz[u] = 1;
  f[u][0] = 0;
  f[u][1] = value[u];
  for (int e = H[u]; e; e = E[e].nt) {
    int v = E[e].to;
    if (v == ft) {
      continue;
    }
    dfs1(v, u);
    if (siz[son[u]] < siz[v]) {
      son[u] = v;
    }
    siz[u] += siz[v];
    f[u][0] += max(f[v][1], f[v][0]);
    f[u][1] += max(0, f[v][0]);
  }
}

void dfs2(int u, int tp) {
  top[u] = tp;
  dfn[u] = ++dfc;
  bck[dfc] = u;
  g[u][0] = 0;
  g[u][1] = value[u];
  bot[tp] = u;
  if (son[u]) {
    dfs2(son[u], tp);
  }
  for (int e = H[u]; e; e = E[e].nt) {
    int v = E[e].to;
    if (v == fa[u] || v == son[u]) {
      continue;
    }
    dfs2(v, v);
    g[u][0] += max(f[v][0], f[v][1]);
    g[u][1] += f[v][0];
  }
}

namespace segmentTree {
  Matrix tr[N << 2];
  
  void pushup(int x) {
    tr[x] = tr[x << 1] * tr[x << 1 | 1];
  }
  
  void build(int x, int l, int r) {
    if (l == r) {
      tr[x] = Matrix(g[bck[l]][0], g[bck[l]][0], g[bck[l]][1], -inf);
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }
  
  void modify(int x, int l, int r, int p) {
    if (l == r) {
      tr[x] = Matrix(g[bck[l]][0], g[bck[l]][0], g[bck[l]][1], -inf);
      return;
    }
    int mid = (l + r) >> 1;
    p <= mid ? modify(x << 1, l, mid, p) : modify(x << 1 | 1, mid + 1, r, p);
    pushup(x);
  }
  
  Matrix query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tr[x];
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) {
      return query(x << 1, l, mid, ql, qr);
    }
    if (ql > mid) {
      return query(x << 1 | 1, mid + 1, r, ql, qr);
    }
    return query(x << 1, l, mid, ql, mid) * query(x << 1 | 1, mid + 1, r, mid + 1, qr);
  }
}

using namespace segmentTree;

void debug() {
  cout << "F: " << '\n';
  for (int i = 1; i <= n; i++) {
    cout << i << ' ' << f[i][0] << ' ' << f[i][1] << '\n';
  }
  cout << "G: "<< '\n';
  for (int i = 1; i <= n; i++) {
    cout << i << ' ' << g[i][0] << ' ' << g[i][1] << '\n';
  }
}

int main() {
  read(n), read(m);
  for (int i = 1; i <= n; i++) {
    read(value[i]);
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 0);
  dfs2(1, 1);
//  cout << "pre work" << '\n';
//  debug();
//  cout << "pre work end" << '\n';
  build(1, 1, n);
//  for (int i = 1; i <= n; i++) {
//    cout << "no " << i << query(1, 1, n, dfn[i], dfn[i]) << '\n';
//  }
  while (m--) {
    int x, y;
    read(x), read(y);
    g[x][1] += y - value[x];
    value[x] = y;
    while (x) {
      Matrix former = query(1, 1, n, dfn[top[x]], dfn[bot[top[x]]]);
      modify(1, 1, n, dfn[x]);
      Matrix latter = query(1, 1, n, dfn[top[x]], dfn[bot[top[x]]]);
      x = top[x];
      g[fa[x]][0] += max(latter[0][0], latter[1][0]) - max(former[0][0], former[1][0]);
      g[fa[x]][1] += latter[0][0] - former[0][0];
      x = fa[x];
    }
//    debug();
    Matrix ans = query(1, 1, n, dfn[1], dfn[bot[1]]);
//    cout << ans << '\n';
    writeln(max(ans[0][0], ans[1][0]));
  }
  return 0;
}
最后修改:2020 年 02 月 21 日 01 : 03 AM
如果觉得我的文章对你有用,请随意赞赏