树上路径问题—树形dp
title: 树上路径问题—树形dp
categories:
- ICPC
tags:
- null
abbrlink: b48701c5
date: 2024-01-05 00:00:00
树上路径问题—树形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=给定一棵 $n$ 个)
树上路径问题常见手法:树上动态规划(路径问题) - 算法小站 (ringalgo.com)
1.一般是在LCA处考虑路径,也可能是最低点
2.两种方法,记录每个点他在哪条路径,直接在LCA处考虑这条路径选或者不选(树上路径1的两种方法)
3.一般第一种方法更加常用,因为记录了一些额外的信息,所以更能处理更加复杂的问题,但是由于是两维的所以 它的复杂度基本最低就是$n^2$的,而第二种是一维的所以更容易考虑优化
1.树上路径1:给你一个 $n(1≤n≤2000)$个点的树和 $m(1≤m≤2000)$ 条树上的简单路径,每个路径有个权值 $ai(1≤ai≤10^9)$。要求选择一些路径,使得每个点至多在一条路径上,并且路径的权值和最大。
Sol:考虑选若干条不交的路径使得权值和最大。
思路1:时间复杂度O(nm)
$ f[i][j]$:表示i这个子树,穿过i这个点的是j这条路径。如果j是0的话,就说明,选择的路径里面没有路径穿过i这个点
g[i]:表示i这个子树没有路径伸出来(伸向父亲)的最大值 。
转移: $f[i][j]$值计算:
$j==0$的时候,i的每个子树都是独立的,所以需要求和每个封闭儿子子树的最大值即可,
$j>0$的时候,加入儿子v也在这条路径上面,$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]$表示考虑i这个子树能获得的最大权值(不考虑从i这个子树里面伸出来的子树) 转移:
- i这个点不在任何一个路径里面,所以他的所有儿子全是封闭的,直接求和就行了
- i如果在某一条路径里面的话,他必然是这条路径的最高点,所以对于每一条路径,就是在他的最高点考虑是否选择这条路径,由于选择的路径是不交的,所以假设现在i通过的路径是j,那么j这条路径上的点都不能在其他路径上面 了,所以j这条路径上节点的儿子都是封闭的,也就是$\sum g[这些伸出来的儿子]$
优化:如果能够支持删除路径上的所有点后面快速求出剩下点的dp值的话,
问题就会被优化到O(n+mlogn),这个可以使用DFS序和树状数组来解决
实现小技巧:在dfs的过程中,发现路径每次往下延申1,那么带来的变化就是该节点的所有儿子的dp值之和减去该节点的dp值。失去的是这个点的封闭,得到儿子的封闭。
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次$
不能简单地考虑删除路径上的点,进行 dp 转移
分析一下如何定义状态:贪心思考对于经过u向上延申的path1,path2,我们应该希望其尽可能向上覆盖。$f[i][j]$:表示i这个子树里面选择的路径能够最多向上延申到j这个深度的最小权值。
转移:考虑子树,当合并两个子树的时候$f[v1][j1],f[v2][j2]$,那么最多能够延申的位置就是$min(j1, j2)$(越靠上深度越浅)。另外还需要考虑的是以i这个点为最低点的线段的情况 ,这里本质上就是对于每条路径在最低处考虑选不选这条路径。具体合并过程就是
//子树暴力合并到当前根
过程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(n^3)$。因为一个子树可能很小,但是他的j可能比较比较大,所以有效的状态j就很大了,枚举的时候需要跑满上界,所以和子树大小无关,不能用siz上下界优化。
考虑一个trick:记录一个后缀最小值 ,则可以优化到$O(n^2)$.抽象一下,就是给你一个a,b数组,让你$O(n)$求出c数组,c的定义如下$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]+bj)}$。可以维护a,b的后缀最小值数组sufa,sufb。
则$c[i]=min{(sufa[j]+b[i]),(a[i]+sufb[j])}$
#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;
}