树上路径问题—树形dp

[「REMAKE系列」树形dp篇 - Roshin - 博客园 (cnblogs.com)](https://www.cnblogs.com/Roshin/p/remake_tree_dp.html#:~:text=树上路径1 link)

dls的树形dp - 牛佳文 - 博客园 (cnblogs.com)

Codeforces 633 F The Chocolate Spree(树形dp，两条不相交链节点权值和最大)_树上求不相交的两条权值最大路径-CSDN博客

SPOJ Two Paths 树上不相交路径乘积最大值_树上最多路径 边不相交路径-CSDN博客

[P9047 [PA2021] Poborcy podatkowi - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P9047#:~:text=给定一棵 nn 个)

树上路径问题常见手法：树上动态规划（路径问题） - 算法小站 (ringalgo.com)

1.一般是在LCA处考虑路径，也可能是最低点

2.两种方法，记录每个点他在哪条路径，直接在LCA处考虑这条路径选或者不选(树上路径1的两种方法)

3.一般第一种方法更加常用，因为记录了一些额外的信息，所以更能处理更加复杂的问题，但是由于是两维的所以 它的复杂度基本最低就是n2n^2的，而第二种是一维的所以更容易考虑优化

1.树上路径1:给你一个 n(1≤n≤2000)n(1≤n≤2000)个点的树和 m(1≤m≤2000)m(1≤m≤2000) 条树上的简单路径，每个路径有个权值 ai(1≤ai≤109)ai(1≤ai≤10^9)。要求选择一些路径，使得每个点至多在一条路径上，并且路径的权值和最大。

Sol:考虑选若干条不交的路径使得权值和最大。

思路1：时间复杂度O(nm)

$ f[i][j]$：表示i这个子树，穿过i这个点的是j这条路径。如果j是0的话，就说明，选择的路径里面没有路径穿过i这个点

g[i]:表示i这个子树没有路径伸出来(伸向父亲)的最大值 。

转移： f[i][j]f[i][j]值计算：

  • j==0j==0的时候，i的每个子树都是独立的，所以需要求和每个封闭儿子子树的最大值即可，

  • j>0j>0的时候，加入儿子v也在这条路径上面，f[u][j]=f[v][j]+∑vv∈son[u],vv≠vg[vv]f[u][j]=f[v][j]+\sum_{vv\in son[u],vv \ne v}g[vv]

g[i]值计算： i的所有儿子子树都没有伸出来 i是通过他的路径的最高点。然后发现如果考虑清楚g的计算，就可以直接抛弃f，详细见解法2.

解法2：时间复杂度O(nm)

g[i]g[i]表示考虑i这个子树能获得的最大权值(不考虑从i这个子树里面伸出来的子树) 转移:

  • i这个点不在任何一个路径里面，所以他的所有儿子全是封闭的，直接求和就行了
  • i如果在某一条路径里面的话，他必然是这条路径的最高点，所以对于每一条路径，就是在他的最高点考虑是否选择这条路径，由于选择的路径是不交的，所以假设现在i通过的路径是j，那么j这条路径上的点都不能在其他路径上面 了，所以j这条路径上节点的儿子都是封闭的，也就是∑g[这些伸出来的儿子]\sum g[这些伸出来的儿子]

优化：如果能够支持删除路径上的所有点后面快速求出剩下点的dp值的话，

问题就会被优化到O(n+mlogn),这个可以使用DFS序和树状数组来解决

实现小技巧：在dfs的过程中，发现路径每次往下延申1，那么带来的变化就是该节点的所有儿子的dp值之和减去该节点的dp值。失去的是这个点的封闭，得到儿子的封闭。

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
const int N = 2010;
// f[i]:表示i这个子树在内部选直线的最大值
// sf[i]:表示不选经过i的直线，在子树里面选直线的最大值
LL f[N], sf[N];
int fa[N], depth[N];
vector<int> son[N];
vector<array<int, 3> > path[N];
void dfs(int u) {
    for (auto v : son[u]) {
        dfs(v);
        sf[u] += f[v];
    }
    // f[u]初始化成所有儿子内部自己选的情况!!!!
    f[u] = sf[u];  // 后面选直线的时候会消除贡献的
    for (auto p : path[u]) {
        // u是一定在p直线上的，现在假设所有儿子是封闭的，那么求和就是sf了
        // 但是有些儿子其实并不是封闭的，他是在p这条直线上的，那么我们就需要在tmp的基础上进行弥补了
        // 假设他的某个儿子是在p这条直线上的，那么我们就需要减去他本来提供的贡献f[这个儿子],然后再假设
        // 这个儿子的所有儿子都是封闭的，把他们的所有sf加起来，最终到了直线的端点也就结束了
        // 但是下面的实现中，其实是倒着来的，他是从端点向上进行的
        LL tmp = sf[u];
        int p0 = p[0];
        while (p0 != u) {
            tmp += sf[p0] - f[p0];
            p0 = fa[p0];
        }
        int p1 = p[1];
        while (p1 != u) {
            tmp += sf[p1] - f[p1];
            p1 = fa[p1];
        }
        tmp += p[2];
        f[u] = max(f[u], tmp);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 2; i <= n; i++) {
        scanf("%d", &fa[i]);
        son[fa[i]].push_back(i);
        // 深度主要用来暴力求lca
        depth[i] = depth[fa[i]] + 1;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, a;
        scanf("%d %d %d", &u, &v, &a);
        // 数据范围比较小，所以可以暴力地往上跳，第一个次跳到相同的位置就是lca了
        // 这种dp的话，只在lca的位置对路径进行计算
        // 然后我们把路径挂到lca的vector上
        int x = u, y = v;
        while (x != y) {
            // 每次将深度大的往上跳
            if (depth[x] > depth[y])
                x = fa[x];
            else
                y = fa[y];
        }
        path[x].push_back({u, v, a});
    }
    dfs(1);
    printf("%lld\n", f[1]);
    return 0;
}

2.树上路径2

问题描述
给定一个n个点的有根树，m条简单路径，每个路径有一个权值，并且这些路径都是一个点到它的祖先
要求选择一些路径，使得每个点至少在一条路径上，并且路径权值和最小

Sol:这个问题和上个问题的区别在于，一个点可能在多条路径上，所以用之前的做法很难。

  • 如果在最高点考虑路径的话，很难转移，因为子树的每个点可能被覆盖⩾1次⩾1次
    不能简单地考虑删除路径上的点，进行 dp 转移

分析一下如何定义状态:贪心思考对于经过u向上延申的path1,path2,我们应该希望其尽可能向上覆盖。f[i][j]f[i][j]:表示i这个子树里面选择的路径能够最多向上延申到j这个深度的最小权值。

转移：考虑子树，当合并两个子树的时候f[v1][j1],f[v2][j2]f[v1][j1],f[v2][j2],那么最多能够延申的位置就是min(j1,j2)min(j1, j2)(越靠上深度越浅)。另外还需要考虑的是以i这个点为最低点的线段的情况 ，这里本质上就是对于每条路径在最低处考虑选不选这条路径。具体合并过程就是

1
2
3
4
5
6
7
8
9
10
//子树暴力合并到当前根
过程for (int i = 1; i <= dep[u]; i++) {
    for (int j = 1; j <= dep[v];j++) {
        tmp[min(i, j)] == min(tmp[min(i, j)], dp[u][i] + dp[v][j]);
    }
}
//tmp数组复制给dp[u]
for(int i=1;i<=dep[v];i++)dp[u][i]=tmp[i];
//再考虑最低点挂载在u点的所有路径
for(auto[u,v,val])dp[u][dep[v]]=min(dp[u][dep[v]],val);

但这样直接做的复杂度是O(n3)O(n^3)。因为一个子树可能很小，但是他的j可能比较比较大，所以有效的状态j就很大了，枚举的时候需要跑满上界，所以和子树大小无关，不能用siz上下界优化。

  • 考虑一个trick：记录一个后缀最小值 ，则可以优化到O(n2)O(n^2).抽象一下，就是给你一个a,b数组，让你O(n)O(n)求出c数组,c的定义如下c[min(i,j)]=min1≤i,j≤n(a[i]+b[j])c[min(i,j)]=min_{1 \le i,j \le n}({a[i]+b[j]})

  • 考虑c[i]=min((j>=i)a[j]+b[i]),(a[i]+b[j](j>=i))c[i]=min{((j>=i)a[j]+b[i]),(a[i]+b[j](j>=i))}。可以维护a,b的后缀最小值数组sufa,sufb。

  • 则c[i]=min(sufa[j]+b[i]),(a[i]+sufb[j])c[i]=min{(sufa[j]+b[i]),(a[i]+sufb[j])}

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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2010;
const LL inf = 1ll << 60;
vector<int> son[N];
vector<array<int, 2>> path[N];
LL f[N][N];
int depth[N];
int n, m;

void merge(LL a[], LL b[], int len) {
    static LL sufa[N], sufb[N];
    // 当我们合并两个背包的时候，发现是f[u][i]和f[v][j]合并到一个背包里面，当我们暴力枚举i，j的话
    // 他的复杂度比较高，是接近O(n^3)的
    // 我们可以进行前缀或者后缀的处理，这种技巧感觉挺常用的
    // 我们处理一个后缀的i,j的最小值,
    // 那么就是f[u][min(i, j)] + min(f[v][j>=min(i, j)])
    // 和min(f[u][>=min(i, j)]) + f[v][min(i, j)]
    sufa[len + 1] = inf;
    sufb[len + 1] = inf;
    for (int i = len; i >= 1; i--) {
        sufa[i] = min(sufa[i + 1], a[i]);
        sufb[i] = min(sufb[i + 1], b[i]);
    }

    for (int i = 1; i <= len; i++) {
        a[i] = min(a[i] + sufb[i], b[i] + sufa[i]);
    }
}

void dfs(int u) {
    // static LL tmp[N];
    for (int i = 1; i <= depth[u]; i++) f[u][i] = inf;
    // 为什么这样进行赋值，因为这里是按照树上背包做的，我们每次都在合并一个背包，所以最开的时候是没有儿
    // 子的情况，之后我们再慢慢地进行合并
    for (auto p : path[u]) f[u][depth[p[0]]] = min(f[u][depth[p[0]]], (LL)(p[1]));
    for (auto v : son[u]) {
        dfs(v);
        // 暴力写法
        // 这里要根据实际的含义进行转移
        // 在最开始的没有进入这个循环的时候,f[u][depth[v]]确实是零
        // 但是当开始了一些分支之后f[u][depth[v]]就不一定是零了，可能下面的儿子向上延申刚好到depth[v]
        // 所以状态转移需要保留着这些
        // for(int i = 1; i <= depth[v]; i ++) tmp[i] = inf;
        // for(int i = 1; i <= depth[v]; i ++){
        //     for(int j = 1; j <= depth[v]; j ++){
        //         tmp[min(i, j)] = min(f[u][i] + f[v][j], tmp[min(i, j)]);
        //     }
        // }
        // for(int i = 1; i <= depth[v]; i ++) f[u][i] = tmp[i];
        merge(f[u], f[v], depth[v]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    depth[1] = 1;
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        son[x].push_back(i);
        depth[i] = depth[x] + 1;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, a;
        scanf("%d %d %d", &u, &v, &a);
        path[v].push_back({u, a});
    }

    dfs(1);
    // 为什么这里不能直接==(1ll<<60),因为他可能在更新的时候加上了一些东西
    if (f[1][1] >= (1ll << 60) / 2)
        puts("-1");
    else
        printf("%lld\n", f[1][1]);

    return 0;
}