[心之碎片II] - 0901-0908 树上问题和几个树形/状压DP

柿子饼同学

在线问题常常考虑离线, 可以排序之类的操作然后减少复杂度, 得出答案(差分 / 删除转加入 ...), 能够自己确定一个 "顺序"
dp 最先考虑的是阶段, 就是给出一个顺序来解决问题, 转移的时候注意一下有没有漏
在需要枚举子集的 dp 中常常考虑容斥, 允许他们重复, 先弱化题目要求, 如果我们知道集合的交就能知道他们的并
树形的倍增 dp 套路是 i 到 i 的祖先, 挖掉 i 的子树的答案
树形背包的套路需要掌握参数别写错!!! 排序后的东西一次性搞完, 后面的顺序是错的

P4219 [BJOI2014] 大融合
简单题, 用并查集实时维护连通块, 并查集的根是树上最高的节点

P5024 [NOIP2018 提高组] 保卫王国
原来已经差不多想好了, 但是倍增数组的设计还是取到了 i , 导致不好转移
倍增数组求答案的时候我们只关系结尾的状态, 所以枚举怎么得出结尾状态即可, 要设置中间量 = 原来的量 + 这次倍增的量, 最后取最大值

ll Solve(int a, int x, int b, int y){
    if(dep[a] < dep[b]){
        swap(a, b);
        swap(x, y);
    }

    if(pa[a][0] == b && !x && !y) return -1;

    ll ta[2], tb[2];
    ll ra[2] = {INF, INF}, rb[2] = {INF, INF};

    // ra/rb 为结果数组
    // ta/tb 为转移中间量

    ra[x] = dn[a][x];
    rb[y] = dn[b][y];

    int d = dep[a] - dep[b];
    for(int i = 16; i >= 0; i--){
        if((d >> i) & 1){
            ta[0] = ta[1] = INF;

            for(int j = 0; j < 2; j++){
                for(int k = 0; k < 2; k++){
                    ta[k] = min(ta[k], ra[j] + f[a][i][j][k]);
                }
            }

            ra[0] = ta[0], ra[1] = ta[1];
            a = pa[a][i];
        }
    }

    if(a == b)
        return (ra[y] + up[b][y]);

    for(int i = 16; i >= 0; i--){
        if(pa[a][i] == pa[b][i]) continue;

        ta[0] = ta[1] = INF;
        tb[0] = tb[1] = INF;

        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                ta[k] = min(ta[k], ra[j] + f[a][i][j][k]);
                tb[k] = min(tb[k], rb[j] + f[b][i][j][k]);
            }
        }

        for(int j = 0; j < 2; j++){
            ra[j] = ta[j];
            rb[j] = tb[j];
        }

        a = pa[a][i], b = pa[b][i];
    }

    int l = pa[a][0];
    ll res = INF;

    res = min(res, dn[l][0] - dn[a][1] - dn[b][1] + ra[1] + rb[1] + up[l][0]);
    res = min(res, dn[l][1] - min(dn[a][0], dn[a][1]) - min(dn[b][0], dn[b][1]) + min(ra[1], ra[0]) + min(rb[0], rb[1]) + up[l][1]);

    return res;
}

P5298 [PKUWC2018] Minimax
线段树合并, 公式好推但是没能想出来合并的时候怎么办的
首先发现是对于每个 i 有不同的前后缀, 那么要想到只更新叶子, 然后更新更大的区间
注意需要保存没更新前的值, 到达叶子的时候正好能算出来对应值

// 线段树合并的同时, 到达叶子节点就可以更新它的值了
int Merge(int x, int y, ll px, ll py, ll sx, ll sy, ll p){
    if(!x && !y) return 0;

    // 到达叶子节点, 正好在路途中就求出了另一个孩子的前缀后缀
    if(!y){
        t[x].tag((p * py % P + (1 - p + P) * sy % P) % P);
        return x;
    }
    if(!x){
        t[y].tag((p * px % P + (1 - p + P) * sx % P) % P);
        return y;
    }

    Dn(x), Dn(y);
    // 保证都是之前的答案
    ll lx = f(lc(x)), rx = f(rc(x)), ly = f(lc(y)), ry = f(rc(y));

    // 根据走向更新一下前后缀
    lc(x) = Merge(lc(x), lc(y), px, py, (sx + rx) % P, (sy + ry) % P, p);
    rc(x) = Merge(rc(x), rc(y), (px + lx) % P, (py + ly) % P, sx, sy, p);

    Up(x);
    return x;
}

P4563 [JXOI2018] 守卫
想了一个假做法, 预处理 r 能看到的最远连续, 但是不对劲, 发现的性质是 r 必须建一个
区间 dp 想想怎么区分 左 / 右 的 dp 从而更新整个的

// 对于一段区间 [l, r] r是必须取的, 根据这个来做
    for(int r = 1; r <= n; r++){
        f[r][r] = 1;
        ans ^= 1;

        int p = 0;
        for(int l = r - 1; l >= 1; l--){
            // 对于每个 r, 能看到的区间是 p1...p2...p3...p4... 等等
            // 点点点的那些区间没法被看见, 需要自己解决
            // 每次找到 r 能看见的最远点, 没被更新的时候就是...的区间
            // 对于...的区间要么在 p 建, 要么在 p - 1 建
            if(!p || Insight(l, p, r)) p = l;

            f[l][r] = min(f[l][p], f[l][p - 1]) + f[p + 1][r];
            ans ^= f[l][r];
        }
    }

P3349 [ZJOI2016] 小星星
I - 状压 dp 比较简单, 但是转移复杂度太高, 一个优化是把状态按照 1 的个数分类, 这样能显著提升时间, 值得学习 (90 pts)

for(int i = 1; i < (1 << n); i++){
    st[popcnt(i)].emplace_back(i);
}

II - 正解是容斥, 以后看到这种类似的需要枚举子集的问题 (而且不重叠的) 想容斥, 我们允许算重复, 但是只能根据枚举的状态里面的数来算
根节点是 0 ,注意了

void Assign(int st){
    siz = 0;
    for(int i = 0; i < n; i++){
        if((st >> i) & 1){
            c[++siz] = i + 1;
        }
    }
}

void Calc(){
    ll t = 1;
    if((n - siz) & 1) t = -1;

    for(int i = 1; i <= siz; i++){
        ans += t * f[1][c[i]];
    }
}

void dfs(int u, int p){
    for(int i = 1; i <= siz; i++){
        f[u][c[i]] = 1;
    }
    for(auto v : e[u]){
        if(v == p) continue;

        dfs(v, u);

        for(int i = 1; i <= siz; i++){
            ll s = 0;
            for(int j = 1; j <= siz; j++){
                if(mp[c[i]][c[j]]) s += f[v][c[j]];

            }
            f[u][c[i]] *= s;
        }
    }
}

P4516 [JSOI2018] 潜入行动
状态是想对了, 败在没有考虑清楚谁能转移到谁, 导致漏, 一定要注意
另外, 树上背包的板子需要记住

P4216 [SCOI2015] 情报传递
没啥, 主要是遇到题目多想想离线做法, 可以有序的加进去东西
询问排序之后一定要一次性解决完, 不然会错

P3979 遥远的国度
注意参数不要写错, dfn 的最大值是 n, 而不是 dfn[n]

P3959 [NOIP2017 提高组] 宝藏
一定确定阶段再想, 不要乱想, 枚举子集可以用 mask

memset(f, 0x3f, sizeof(f));
for(int i = 0; i < n; i++){
    f[0][(1 << i)] = 0;
}

for(int i = 1; i < n; i++){
    for(int st2 = 0; st2 < (1 << n); st2++){
        for(int st1 = st2; st1; st1 = (st1 - 1) & st2){
            if(c[st1][st2] == -1) continue;

            f[i][st2] = min(f[i][st2], f[i - 1][st1] + c[st1][st2] * i);
        }
    }
}

for(int i = 0; i < n; i++){
    ans = min(ans, f[i][(1 << n) - 1]);
}

FishC

看得出来，你在进行一系列树形结构和树形动态规划（DP）问题的研究。以下是对你提出的一些具体问题和方法的简明解答：

### 并查集（Union-Find）和连通分量的维护

#### P4219 大融合
- **问题**：你需要实时维护连通分量（组件）。
- **方法**：使用并查集（Union-Find）来维护连通块，并确保并查集的根是树的最高节点。

class UnionFind {
  public:
      vector<int> parent, rank;
      
      UnionFind(int n) : parent(n), rank(n, 0) {
          for (int i = 0; i < n; ++i) parent[i] = i;
      }
      
      int find(int u) {
          if (u != parent[u])
              parent[u] = find(parent[u]);
          return parent[u];
      }
      
      void unite(int u, int v) {
          int root_u = find(u);
          int root_v = find(v);
          if (root_u != root_v) {
              if (rank[root_u] < rank[root_v])
                  parent[root_u] = root_v;
              else if (rank[root_u] > rank[root_v])
                  parent[root_v] = root_u;
              else {
                  parent[root_v] = root_u;
                  rank[root_u]++;
              }
          }
      }
  };

  用这个并查集实时维护你的连通块。

### 倍增（Binary Lifting）与树上 DP

#### P5024 保卫王国
- **问题**：使用倍增（Binary Lifting）来解决祖先节点问题，并通过动态规划计算最优结果。
- **方法**：记录每一层的最大值并逐层更新。

const int INF = 1e9;
  const int MAXN = 100005;
  const int MAX_LOG = 17;
  
  vector<int> parent[MAXN][MAX_LOG];
  vector<int> dep(MAXN);
  vector<ll> f[MAXN][2][2]; // dp array

  void preprocess(vector<vector<int>>& adj, int u, int p) {
      parent[u][0] = p;
      for (int i = 1; i < MAX_LOG; i++)
          parent[u][i] = parent[parent[u][i-1]][i-1];
      
      for (int v : adj[u]) {
          if (v != p) {
              dep[v] = dep[u] + 1;
              preprocess(adj, v, u);
          }
      }
  }

  ll solve(int a, int x, int b, int y) {
      if (dep[a] < dep[b]) swap(a, b), swap(x, y);

      if (parent[a][0] == b && !x && !y) return -1;

      ll ta, tb;
      ll ra = {INF, INF}, rb = {INF, INF};
      
      ra[0] = ra[1] = 0;
      rb[0] = rb[1] = 0;

      int d = dep[a] - dep[b];
      for (int i = 0; i < MAX_LOG; i++) {
          if ((d >> i) & 1) {
              ta[0] = ta[1] = INF;
              for (int j = 0; j < 2; j++) {
                  for (int k = 0; k < 2; k++) {
                      ta[k] = min(ta[k], ra[j] + f[a][j][k]);
                  }
              }
              ra[0] = ta[0];
              ra[1] = ta[1];
              a = parent[a][i];
          }
      }

      if (a == b) return min(ra[0] + up[a][0], ra[1] + up[a][1]);

      for (int i = MAX_LOG-1; i >= 0; i--) {
          if (parent[a][i] != parent[b][i]) {
              ta[0] = ta[1] = tb[0] = tb[1] = INF;
              for (int j = 0; j < 2; j++) {
                  for (int k = 0; k < 2; k++) {
                      ta[k] = min(ta[k], ra[j] + f[a][j][k]);
                      tb[k] = min(tb[k], rb[j] + f[b][j][k]);
                  }
              }
              ra[0] = ta[0];
              ra[1] = ta[1];
              rb[0] = tb[0];
              rb[1] = tb[1];
              a = parent[a][i];
              b = parent[b][i];
          }
      }

      int l = parent[a][0];
      ll res = min({ra[0] + rb[0] + up[l][0], ra[1] + rb[1] + up[l][1]});
      return res;
  }

  这个代码框架可以解决节点 \(a\) 和 \(b\) 的 LCA（最近公共祖先）问题，并基于倍增法进行优化。

这些方法都是经典的树和树上的动态规划问题解决方法，希望对你有所帮助。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

柿子饼同学

@zhangjinxuan 最近怎么样, 开学之后就忙起来了呢

FishC

柿子饼同学 发表于 2024-09-08 20:31
@zhangjinxuan 最近怎么样, 开学之后就忙起来了呢

你好！开学之后确实会有更多的事情需要处理，希望你现在适应得不错。看你在研究树形结构和动态规划的问题，这些都是很重要且具有挑战性的课题。如果有任何具体的问题需要解答，随时欢迎提问！我们一起努力，共同进步。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangjinxuan

goodgood

某一个“天”

很cool的阳

曾热爱这世界

c

森林格格屋

谢谢

简柠啦

XiaoMengXin-1

回帖奖励

OKMY

+

kerln888

回帖奖励

harryhan123

?