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

柿子饼同学

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

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

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

1. ll Solve(int a, int x, int b, int y){
   
2.     if(dep[a] < dep[b]){
   
3.         swap(a, b);
   
4.         swap(x, y);
   
5.     }
   
6. 
   
7.     if(pa[a][0] == b && !x && !y) return -1;
   
8. 
   
9.     ll ta[2], tb[2];
   
10.     ll ra[2] = {INF, INF}, rb[2] = {INF, INF};
    
11. 
    
12.     // ra/rb 为结果数组
    
13.     // ta/tb 为转移中间量
    
14. 
    
15.     ra[x] = dn[a][x];
    
16.     rb[y] = dn[b][y];
    
17. 
    
18.     int d = dep[a] - dep[b];
    
19.     for(int i = 16; i >= 0; i--){
    
20.         if((d >> i) & 1){
    
21.             ta[0] = ta[1] = INF;
    
22. 
    
23.             for(int j = 0; j < 2; j++){
    
24.                 for(int k = 0; k < 2; k++){
    
25.                     ta[k] = min(ta[k], ra[j] + f[a][i][j][k]);
    
26.                 }
    
27.             }
    
28. 
    
29.             ra[0] = ta[0], ra[1] = ta[1];
    
30.             a = pa[a][i];
    
31.         }
    
32.     }
    
33. 
    
34.     if(a == b)
    
35.         return (ra[y] + up[b][y]);
    
36. 
    
37.     for(int i = 16; i >= 0; i--){
    
38.         if(pa[a][i] == pa[b][i]) continue;
    
39. 
    
40.         ta[0] = ta[1] = INF;
    
41.         tb[0] = tb[1] = INF;
    
42. 
    
43.         for(int j = 0; j < 2; j++){
    
44.             for(int k = 0; k < 2; k++){
    
45.                 ta[k] = min(ta[k], ra[j] + f[a][i][j][k]);
    
46.                 tb[k] = min(tb[k], rb[j] + f[b][i][j][k]);
    
47.             }
    
48.         }
    
49. 
    
50.         for(int j = 0; j < 2; j++){
    
51.             ra[j] = ta[j];
    
52.             rb[j] = tb[j];
    
53.         }
    
54. 
    
55.         a = pa[a][i], b = pa[b][i];
    
56.     }
    
57. 
    
58.     int l = pa[a][0];
    
59.     ll res = INF;
    
60. 
    
61.     res = min(res, dn[l][0] - dn[a][1] - dn[b][1] + ra[1] + rb[1] + up[l][0]);
    
62.     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]);
    
63. 
    
64.     return res;
    
65. }

复制代码

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

1. // 线段树合并的同时, 到达叶子节点就可以更新它的值了
   
2. int Merge(int x, int y, ll px, ll py, ll sx, ll sy, ll p){
   
3.     if(!x && !y) return 0;
   
4. 
   
5.     // 到达叶子节点, 正好在路途中就求出了另一个孩子的前缀后缀
   
6.     if(!y){
   
7.         t[x].tag((p * py % P + (1 - p + P) * sy % P) % P);
   
8.         return x;
   
9.     }
   
10.     if(!x){
    
11.         t[y].tag((p * px % P + (1 - p + P) * sx % P) % P);
    
12.         return y;
    
13.     }
    
14. 
    
15.     Dn(x), Dn(y);
    
16.     // 保证都是之前的答案
    
17.     ll lx = f(lc(x)), rx = f(rc(x)), ly = f(lc(y)), ry = f(rc(y));
    
18. 
    
19.     // 根据走向更新一下前后缀
    
20.     lc(x) = Merge(lc(x), lc(y), px, py, (sx + rx) % P, (sy + ry) % P, p);
    
21.     rc(x) = Merge(rc(x), rc(y), (px + lx) % P, (py + ly) % P, sx, sy, p);
    
22. 
    
23.     Up(x);
    
24.     return x;
    
25. }

复制代码

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

1. // 对于一段区间 [l, r] r是必须取的, 根据这个来做
   
2.     for(int r = 1; r <= n; r++){
   
3.         f[r][r] = 1;
   
4.         ans ^= 1;
   
5. 
   
6.         int p = 0;
   
7.         for(int l = r - 1; l >= 1; l--){
   
8.             // 对于每个 r, 能看到的区间是 p1...p2...p3...p4... 等等
   
9.             // 点点点的那些区间没法被看见, 需要自己解决
   
10.             // 每次找到 r 能看见的最远点, 没被更新的时候就是...的区间
    
11.             // 对于...的区间要么在 p 建, 要么在 p - 1 建
    
12.             if(!p || Insight(l, p, r)) p = l;
    
13. 
    
14.             f[l][r] = min(f[l][p], f[l][p - 1]) + f[p + 1][r];
    
15.             ans ^= f[l][r];
    
16.         }
    
17.     }

复制代码

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

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

复制代码

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

1. void Assign(int st){
   
2.     siz = 0;
   
3.     for(int i = 0; i < n; i++){
   
4.         if((st >> i) & 1){
   
5.             c[++siz] = i + 1;
   
6.         }
   
7.     }
   
8. }
   
9. 
   
10. void Calc(){
    
11.     ll t = 1;
    
12.     if((n - siz) & 1) t = -1;
    
13. 
    
14.     for(int i = 1; i <= siz; i++){
    
15.         ans += t * f[1][c[i]];
    
16.     }
    
17. }
    
18. 
    
19. void dfs(int u, int p){
    
20.     for(int i = 1; i <= siz; i++){
    
21.         f[u][c[i]] = 1;
    
22.     }
    
23.     for(auto v : e[u]){
    
24.         if(v == p) continue;
    
25. 
    
26.         dfs(v, u);
    
27. 
    
28.         for(int i = 1; i <= siz; i++){
    
29.             ll s = 0;
    
30.             for(int j = 1; j <= siz; j++){
    
31.                 if(mp[c[i]][c[j]]) s += f[v][c[j]];
    
32. 
    
33.             }
    
34.             f[u][c[i]] *= s;
    
35.         }
    
36.     }
    
37. }

复制代码

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

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

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

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

1. memset(f, 0x3f, sizeof(f));
   
2. for(int i = 0; i < n; i++){
   
3.     f[0][(1 << i)] = 0;
   
4. }
   
5. 
   
6. for(int i = 1; i < n; i++){
   
7.     for(int st2 = 0; st2 < (1 << n); st2++){
   
8.         for(int st1 = st2; st1; st1 = (st1 - 1) & st2){
   
9.             if(c[st1][st2] == -1) continue;
   
10. 
    
11.             f[i][st2] = min(f[i][st2], f[i - 1][st1] + c[st1][st2] * i);
    
12.         }
    
13.     }
    
14. }
    
15. 
    
16. for(int i = 0; i < n; i++){
    
17.     ans = min(ans, f[i][(1 << n) - 1]);
    
18. }

复制代码

FishC

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

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

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

1. class UnionFind {
   
2.   public:
   
3.       vector<int> parent, rank;
   
4.       
   
5.       UnionFind(int n) : parent(n), rank(n, 0) {
   
6.           for (int i = 0; i < n; ++i) parent[i] = i;
   
7.       }
   
8.       
   
9.       int find(int u) {
   
10.           if (u != parent[u])
    
11.               parent[u] = find(parent[u]);
    
12.           return parent[u];
    
13.       }
    
14.       
    
15.       void unite(int u, int v) {
    
16.           int root_u = find(u);
    
17.           int root_v = find(v);
    
18.           if (root_u != root_v) {
    
19.               if (rank[root_u] < rank[root_v])
    
20.                   parent[root_u] = root_v;
    
21.               else if (rank[root_u] > rank[root_v])
    
22.                   parent[root_v] = root_u;
    
23.               else {
    
24.                   parent[root_v] = root_u;
    
25.                   rank[root_u]++;
    
26.               }
    
27.           }
    
28.       }
    
29.   };

复制代码

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

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

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

1. const int INF = 1e9;
   
2.   const int MAXN = 100005;
   
3.   const int MAX_LOG = 17;
   
4.   
   
5.   vector<int> parent[MAXN][MAX_LOG];
   
6.   vector<int> dep(MAXN);
   
7.   vector<ll> f[MAXN][2][2]; // dp array
   
8. 
   
9.   void preprocess(vector<vector<int>>& adj, int u, int p) {
   
10.       parent[u][0] = p;
    
11.       for (int i = 1; i < MAX_LOG; i++)
    
12.           parent[u][i] = parent[parent[u][i-1]][i-1];
    
13.       
    
14.       for (int v : adj[u]) {
    
15.           if (v != p) {
    
16.               dep[v] = dep[u] + 1;
    
17.               preprocess(adj, v, u);
    
18.           }
    
19.       }
    
20.   }
    
21. 
    
22.   ll solve(int a, int x, int b, int y) {
    
23.       if (dep[a] < dep[b]) swap(a, b), swap(x, y);
    
24. 
    
25.       if (parent[a][0] == b && !x && !y) return -1;
    
26. 
    
27.       ll ta, tb;
    
28.       ll ra = {INF, INF}, rb = {INF, INF};
    
29.       
    
30.       ra[0] = ra[1] = 0;
    
31.       rb[0] = rb[1] = 0;
    
32. 
    
33.       int d = dep[a] - dep[b];
    
34.       for (int i = 0; i < MAX_LOG; i++) {
    
35.           if ((d >> i) & 1) {
    
36.               ta[0] = ta[1] = INF;
    
37.               for (int j = 0; j < 2; j++) {
    
38.                   for (int k = 0; k < 2; k++) {
    
39.                       ta[k] = min(ta[k], ra[j] + f[a][j][k]);
    
40.                   }
    
41.               }
    
42.               ra[0] = ta[0];
    
43.               ra[1] = ta[1];
    
44.               a = parent[a][i];
    
45.           }
    
46.       }
    
47. 
    
48.       if (a == b) return min(ra[0] + up[a][0], ra[1] + up[a][1]);
    
49. 
    
50.       for (int i = MAX_LOG-1; i >= 0; i--) {
    
51.           if (parent[a][i] != parent[b][i]) {
    
52.               ta[0] = ta[1] = tb[0] = tb[1] = INF;
    
53.               for (int j = 0; j < 2; j++) {
    
54.                   for (int k = 0; k < 2; k++) {
    
55.                       ta[k] = min(ta[k], ra[j] + f[a][j][k]);
    
56.                       tb[k] = min(tb[k], rb[j] + f[b][j][k]);
    
57.                   }
    
58.               }
    
59.               ra[0] = ta[0];
    
60.               ra[1] = ta[1];
    
61.               rb[0] = tb[0];
    
62.               rb[1] = tb[1];
    
63.               a = parent[a][i];
    
64.               b = parent[b][i];
    
65.           }
    
66.       }
    
67. 
    
68.       int l = parent[a][0];
    
69.       ll res = min({ra[0] + rb[0] + up[l][0], ra[1] + rb[1] + up[l][1]});
    
70.       return res;
    
71.   }

复制代码

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

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

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

柿子饼同学

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

FishC

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

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

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

zhangjinxuan

goodgood

某一个“天”

很cool的阳

曾热爱这世界

c

森林格格屋

谢谢

简柠啦

XiaoMengXin-1

回帖奖励

OKMY

+

kerln888

回帖奖励

harryhan123

?