Part One 树形 dp 基础
1. Computer
题目大意:
给出一棵树,求离每个节点最远的点的距离
(补充说明:树的中心是树中离其他结点的最远距离最近的点 本题只需要对求出的距离取min就是树0的中心到其他点的最远距离)
题目分析
题目要求出结点 u 离其最远的点的距离 ,那么画图我们可以发现 对于结点 u 来说,最大的距离要么为 u 所在子树的正向最大距离要么为 u 父节点方向的最大距离,因此我们需要求出反方向的最大距离,那么反方向的最大距离怎么求呢 ? 画图我们可以知道
1. 倘若结点 u 处在其父节点的正向最大的路径上,最大值要么为父节点的反向最大路径 + w[i] 要么为父节点的正向次大路径 + w[i]
2. 倘若结点 u 不处在其父节点的正向最大路径上,那么最大值要么是父节点的反向最大路径 + w[i] 要么为父节点的正向最大路径 + w[i],那么基于此我们就可以将动态转移方程写出来了
我们设
dp[u][0]:u结点在其子树中最大的正向距离
dp[u][1]:u结点在其子树中次大的正向距离
dp[u][2]:u结点在其子树中反向的最大距离
那么基于上面的分析 我们可以先通过dfs 将子树中最大和次大的正向距离求解出来 在通过判断当前节点是否在正向最大的路径上 分成两种情况
if(dp[j] == vis[u]) dp[j][2] = max(dp[u][2],dp[u][1]) + w[i]
else dp[j][2] = max(dp[u][2],dp[u][0]) + w[i]
那么通过以上的转移方程我们就可以得到各个节点的反向距离了
那么最后的答案该如何表示咧
最大的距离要么为 u 所在子树的正向最大距离 要么为 u 父节点方向的最大距离 因此
ans = max(dp[i][0], dp[i][2]);
AC code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
const int M = 2e4+10;
int h[N], e[M], ne[M], idx , w[M];
int vis[N];
int dp[N][3];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 求出每个结点在其子树中的正向最大距离和正向次大距离
//dp[u][0]:u结点在其子树中最大的正向距离
//dp[u][1]:u结点在其子树中次大的正向距离
//dp[u][2]:u结点在其子树中反向的最大距离
void dfs1(int u,int last)
{
for(int i = h[u]; ~i ;i = ne[i])
{
int j = e[i];
if(j == last) continue;//防止回溯
dfs1(j,u);
if(dp[u][0] < dp[j][0] + w[i])
{
dp[u][0] = dp[j][0] + w[i];//这里是更新最大和
vis[u] = j; //记住经过哪个儿子最大
}
}
for(int i = h[u] ; ~ i ; i = ne[i])
{
int j = e[i];
if(j == last) continue;
if(vis[u] == j) continue;//跳过这个儿子,再剩下点里面找一个最大的,就是这个点次大的
dp[u][1] = max(dp[u][1] , dp[j][0] + w[i]);
}
}
void dfs2(int u,int last)
{
for(int i = h[u] ; ~ i ;i = ne[i])
{
int j = e[i];
if(j == last) continue;
//每个父亲都有两种方式,一个是再往父亲走一步,一个是走父亲的子树
//注意经不经过这个点直接走子树最大和的那个点
if(j == vis[u])//若该儿子结点的方向是正向最大的方向
{
dp[j][2] = max(dp[u][2], dp[u][1]) + w[i];
//那么该节点的反向最大距离 要么是其父亲的反向距离 + 父亲和儿子的距离
//要么是父亲向另外一个方向上的最大距离(整个图的次大距离) + 父亲和儿子的距离
}
else//不是正向最大的方向
{
dp[j][2] = max(dp[u][2],dp[u][0]) + w[i];
//要么是其父亲的反向距离 + 父亲和儿子的距离
//要么是
}
dfs2(j,u);
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
idx = 0;
memset(h, -1, sizeof h);
memset(dp,0,sizeof dp);
for(int i = 2;i <= n;i ++)
{
int a , c;
scanf("%d%d",&a,&c);
add(i,a,c);
add(a,i,c);
}
dfs1(1, -1);
dfs2(1, -1);
for(int i = 1; i <= n; i++)
printf("%d\n", max(dp[i][0], dp[i][2]));
}
return 0;
}
2. Strategic game
题目大意:
求一棵树的最小点覆盖
题目分析
考虑父亲和儿子选取的情况,倘若选取了父亲节点那么儿子则可选可不选,倘若不选取父亲节点那么儿子必须要选
基于此设
dp[u][1] : 选取了 u 这个点 dp[u][0] : 不选取 u 这个点
那么转移方程就写为
dp[u][0] += dp[j][1];
dp[u][1] += min(dp[j][1],dp[j][0]);
AC code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1500 + 10;
const int M = 2 * N ;
int h[N], e[M], ne[M], idx;
bool st[N];
int dp[N][3];//dp[u][1] 表示选了这个点 dp[u][0] 表示不选这个点
void dfs(int u)
{
st[u] = true;
dp[u][1] = 1; dp[u][0] = 0;
for(int i = h[u] ; ~ i ;i = ne[i])
{
int j = e[i];
if(st[j]) continue;
dfs(j);
dp[u][0] += dp[j][1];
dp[u][1] += min(dp[j][1],dp[j][0]);
}
}
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
idx=0;//多组测试 注意初始化
memset(h, -1, sizeof h);
for (int i = 1; i <= n; ++i)
{
int node_num,road_num;
scanf("%d:(%d)", &node_num, &road_num);
while (road_num--)
{
int x;
scanf("%d", &x);
add(node_num,x);
add(x, node_num);
}
}
int ans = 0;
for(int i = 0; i < n; i ++)
{
if(st[i]) continue;
dfs(i);
ans +=min(dp[i][0],dp[i][1]);
}
printf("%d\n",ans);
memset(st,false,sizeof st);
memset(dp,0,sizeof dp);
}
return 0;
}
3. FAR-FarmCraft
题目大意
给定一棵大小为 n 的树,从节点 1 出发需要为树中每个节点安装上软件(节点 1 必须是最后一个安装软件),走过每条边需要花费 1 时间,安装软件又需要花费 cost[i] (到达节点后软件就会开始安装 不用等待其安装完再前往下一个节点) 现在求所有节点都安装完软件的最短时间为多少
题目分析
我们很容易就发现当节点的遍历顺序确定下来时,答案就被确定下来了. 那么我们考虑这样的情况 一个父节点 u 连接着两个子节点 a 和 b 那么我应该先遍历 a 还是先遍历 b 呢, 设 f[x] 表示遍历 x 的子树所需要的时间 Size[x] 表示其节点个数 那么先遍历 a 的话对答案的贡献是 f[b] + Size[a] * 2 + 1 先遍历 b 的话 对答案的贡献则是 f[a] + Size[b] * 2 + 1 假设此时优先遍历 a 为最优解那么 f[b] + Size[a] * 2 + 1 < f[a] + Size[b] * 2 + 1 那么我可以得到 f[b] - 2 * Size[b ] < f[a] - Size[a] 因此我们推断出了遍历的顺序应该按照以上的定义去排序即可 因此核心的转移方程就是 f[u] = max(f[u],now * 2 + f[j] + 1)
AC code
#include<bits/stdc++.h>
using namespace std;
const int N = 500000+100;
vector<int>v[N];
int f[N],Size[N],cost[N];
//f[x] : 遍历第 x 棵子树所花费的时间
//size[a] : a 的子树的节点个数
int n;
bool cmp(int x,int y)
{
return f[x] - Size[x] * 2 > f[y] - Size[y] * 2;
}
void dfs(int u,int fa)
{
int k = v[u].size();
Size[u] = 1;
int now = 0;
if(u != 1) f[u] = cost[u];//不是第一个结点的话 初始的时间需要补上装软件的时间
for(int i = 0;i < k;i ++)
{
int j = v[u][i];//遍历其子节点
if(j == fa) continue;
dfs(j,u);
Size[u] += Size[j];// u 的规模 加上其 子节点的规模
}
sort(v[u].begin(),v[u].end(),cmp);
for(int i = 0;i < k;i ++)
{
int j = v[u][i];
if(j == fa) continue;
f[u] = max(f[u],now * 2 + f[j] + 1);//同上述题目分析的式子
now += Size[j];
}
}
int main()
{
cin>>n;
for(int i = 1;i <= n;i ++) scanf("%d",&cost[i]);
for(int i = 1;i < n; i ++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,0);
printf("%d\n",max(f[1],(n - 1) * 2 + cost[1]));
//倘若最后一个人安装时其他人都已经安装完了那么 时间为 (n - 1) * 2 + cost[1] (最终都会遍历两次所有的边再加上安装的时间)
//以最后所有都结束的时间为准 因此取 max
return 0;
}
Part Two 树上背包
1. 选课
题目大意
现在有 N 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程 a 是课程 b 的先修课即只有学完了课程 a,才能学习课程 b)。一个学生要从这些课程里选择 M 门课程学习,问他能获得的最大学分是多少?
题目分析
比较裸的有依赖的背包问题
不妨设f[now][j][k]表示以 now 为根节点的子树 考虑前 j 个节点选 k 门课的方案数,那么递推的起始点就是 f[now][1][1]=val[now]那么很容易就可以得到f[now][j][k]=max(f[now][j-1][k],f[son][所有节点数][l]+f[now][j-1][k-l]) 那么三维的转移方程已经列出来了 那么现在考虑怎么优化的问题,我要用到j-1的内容 都是满足l<k的 所以倒着循环k 这样就可以使我们在一个数组中当前值和上面我们用到的值完全不影响
因此转移方程如下:
for (int a = m; a >= 0; a --) // 倒序循环当前选课总门数(当前背包体积)
for (int b = 0; b <= a; ++b) // 循环更深子树上的选课门数(组内物品)
f[u][a] = max(f[u][a],f[u][a - b] + f[j][b]);
AC code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310,M = 600+10;
int f[N][N];
int h[N], e[M], ne[M], idx;
int val[N];
int n , m;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
f[u][0] = 0;
for(int i = h[u]; ~ i ;i = ne[i])
{
int j = e[i];
dfs(j);
for (int a = m; a >= 0; a --) // 倒序循环当前选课总门数(当前背包体积)
for (int b = 0; b <= a; ++b) // 循环更深子树上的选课门数(组内物品)
f[u][a] = max(f[u][a],f[u][a - b] + f[j][b]);
}
if(u != 0)
for(int a = m;a > 0;a --) //对于一颗树而言 根节点是一定要选的 所以要为根节点空出位置
f[u][a] = f[u][a - 1] + val[u];
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
{
int x;
cin >> x >> val[i];
add(x , i);
}
dfs(0);
printf("%d\n",f[0][m]);
return 0;
}
2.二叉苹果树
题目大意
每一段树枝上有一些苹果,现在给你 n 个点,需要你保留 m 条树枝,使得保留下的树枝上苹果数量最多
题目分析
与选课几乎可以说是一模一样,都是裸的有依赖的背包问题在这里就不分析了
for(int j = m;j >= 0;j --)
for(int k = 0;k <= j - 1;k ++)
dp[u][j] = max(dp[u][j],dp[u][j - k - 1] + dp[s][k] + w[i]);
AC code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int N = 1000;
const int M = 2 * N;
int h[N], e[M], ne[M], idx, w[M];
//树根编号一定为 1
int dp[N][N];//dp[u][m] 以u为父节点 选取 m 件物品时最大的价值
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int last)
{
for(int i = h[u]; ~ i;i = ne[i])
{
int s = e[i];
if(s == last) continue;
dfs(s,u);
for(int j = m;j >= 0;j --)
for(int k = 0;k <= j - 1;k ++)
dp[u][j] = max(dp[u][j],dp[u][j - k - 1] + dp[s][k] + w[i]);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n - 1;i ++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a, b, c);
add(b, a, c);
}
dfs(1,-1);
printf("%d\n",dp[1][m]);
return 0;
}
Part Three 换根 dp
一些说明
树形 DP 中的换根 DP 问题又被称为二次扫描,通常不会指定根结点,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。通常需要两次 DFS,第一次 DFS 预处理诸如深度,点权和之类的信息,在第二次 DFS 开始运行换根动态规划。
1. STA-Station
题目大意
给定一个包含 n 个节点的树,请你确定一个节点,当树以该节点为根时,所有节点的深度之和最大
题目分析
换根 dp 的大致流程就是两次扫描。首先扫描出给定一根的一些数据,之后再考虑换掉根时,如何进行转移。在本题中,我们定义 dep 为某点子树深度和,Size 存放某点子树结点数,f存放某点向父方向深度和(也有其他实现,在此不表),那么对每个点的dep + f 取最大即可。因此第一次的 dfs 需要搜索出所需的 Size 和 dep ,然后我们再看第二步状态的转移 , 假设 u 是 j 的父节点, 那么从以 u 为根节点的树变成以 j 为根节点的树产生了多大的贡献咧 , 对于 j 的子树上每一个点而言 他的深度统统减一,对于其他的点深度统统加一 因此我们可以列出方程
f[j] + dep[j] = dep[u] + f[u] - Size[j] + n - Size[j]
由以上式子我们移项后可以得到
f[j] = dep[u] - dep[j] + f[u] + n - 2 * Size[j]
由此问题全都被解决了
AC code
#include <iostream>
#include<cstring>
#include <algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const int M = 2 * N;
int n;
LL dep[N],Size[N],f[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//Size[u] : u 子树的节点个数
//dep[u] : u 子树的深度和
//f[u] : 新增的 u 子树深度
void dfs1(int u,int last)
{
//第一次 dfs 搜出状态转移所需的 Size 和 dep
Size[u] = 1;
dep[u] = 0;
for(int i = h[u]; ~ i; i = ne[i])
{
int j = e[i];
if(j == last) continue;
dfs1(j,u);
Size[u] += Size[j];
dep[u] += dep[j] + Size[j];//子树的深度
}
}
void dfs2(int u,int last)
{
//第二次 dfs 做转移
for(int i = h[u]; ~ i ;i = ne[i])
{
int j = e[i];
if(j == last) continue;
//u 的原子树删去 v 子树再加上 u 的父方向新增子树构成的
//f[j] + dep[j] = f[u] + dep[u] + n - 2 * Size[j] => f[j] = f[u] + dep[u] - dep[j] + n - 2 * Size[j]
f[j] = f[u] + dep[u] - dep[j] + n - 2 * Size[j];
dfs2(j,u);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d",&n);
for(int i = 1;i < n;i ++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a, b);
add(b, a);
}
dfs1(1,-1);
dfs2(1,-1);
LL res = 0;
LL node = 1;
for(int i = 1;i <= n;i ++)
{
printf("%lld ",Size[i]);
}
for(int i = 1;i <= n;i ++)
{
if(f[i] + dep[i] > res)
{
res = f[i] + dep[i];
node = i;
}
}
printf("%lld\n",node);
return 0;
}