当前位置: 首页 > news >正文

赛前训练 5 树形 dp

A

做树形 dp 时,尝试将题目转化为只考虑子树内.

对于这个题,因为起点到终点的路径总能拆成 起点 -> LCA -> 终点 的形式,所以我们考虑枚举 LCA 进行 dp.为了使汽油量最大,我们维护 \(dp_i\) 表示子树内跑到 \(i\) 的最大值,\(f_i\) 表示次大值.答案即为 \(\max\{dp_i+f_i+w_i\}\),转移是套路的.

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=3e5+5;
int n,ans;
struct EDGE{int v,w;
};
vector<EDGE> G[N];
int w[N],dp[N],f[N];void dfs(int cur,int fa){for(auto i:G[cur]){if(i.v==fa)continue;dfs(i.v,cur);if(dp[i.v]-i.w+w[i.v]>dp[cur])f[cur]=dp[cur],dp[cur]=dp[i.v]-i.w+w[i.v];else if(dp[i.v]-i.w+w[i.v]>f[cur])f[cur]=dp[i.v]-i.w+w[i.v];}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1,u,v,w;i<n;i++){cin>>u>>v>>w;G[u].push_back({v,w});G[v].push_back({u,w});}dfs(1,0);int ans=-1e18;for(int i=1;i<=n;i++)ans=max(ans,dp[i]+f[i]+w[i]);cout<<ans;return 0;
}

B

这个题是讲过的,关于解法请查阅往期笔记.

错因:对于 dp 状态的定义太模糊.dp 题一定要在草稿纸上写出四要素.

C

两年前的这个时候打的月赛题,当时保龄了(现在估计也差不多).more and more vegetable,what should i do?

首先可以观察出来一些东西:

  • 必然先炸后连,不然有可能把刚连上的炸掉.

  • 由于是森林,最后一定需要 \(n-m-1\) 次操作来维持连通性.

有了上面两条结论,我们就只需要考虑炸的部分了.于是最优化问题很难不想到树形 dp.

分类讨论起手.不难发现,对于每个节点,只有三种情形:

  • 自我毁灭,出边全炸.

  • 保留一个孩子,自己作为链头/链尾.

  • 保留两个孩子,自己作为链的中间点.

自然地,令 \(dp_{i,0/1/2}\),表示节点 \(i\) 全炸/留一个/留两个的最少操作次数.

答案是所有连通块的 \(\min(dp_{root,0},dp_{root,1},dp_{root,2})\) 之和.

转移同样分类讨论:

  • 自我毁灭的情形,它必然还是得把那些炸掉的边连起来,炸的这一次也会付出 \(1\) 的代价,这部分是 \(deg_i+1\) 的;同时,它还需要考虑从子节点转移,子节点三种状态均可,只是如果子节点也是自我毁灭,那么它和父节点连的那条边就会重复算,需要减掉,这部分是 \(\min(dp_{son,0}-1,dp_{son,1},dp_{son,2})\) 的.两部分加起来就好.

  • 留一个的情形,显然我们需要儿子们全都炸了,所以先加上 \(\sum dp_{son,0}\).但我们还得留一个,所以得扣除一个 \(dp_{son,0}\),再加上 \(dp_{son,1}\).那么选哪个儿子最好呢?把后面两项合并为 \(-(dp_{son,0}-dp_{son,1})\),显然减号后面这一坨取 \(\max\) 的时候最优,简单维护即可.

  • 留两个的情形,从留一个出发,我们还得做一遍扣除再加上的操作,但不能和先前留的那一个重合,所以维护一个次大值就好.

于是转移方程就出来了:

iShot_2025-10-04_22.25.08

然后这题就做完了.本题轻微卡常,注意要开 LL.

实现
#include <bits/stdc++.h>
using namespace std;const int N=2e6+5;
int n,m;
int dp[N][3];
bool dfn[N];
vector<int> G[N];void dfs(int cur,int fa){dfn[cur]=1;int fir=0,sec=0;for(int i:G[cur]){if(dfn[i])continue;dfs(i,cur);if(dp[i][0]-dp[i][1]>fir)sec=fir,fir=dp[i][0]-dp[i][1];else if(dp[i][0]-dp[i][1]>sec)sec=dp[i][0]-dp[i][1];dp[cur][0]+=min({dp[i][0]-1,dp[i][1],dp[i][2]});dp[cur][1]+=dp[i][0];}dp[cur][0]+=G[cur].size()+1;dp[cur][1]-=fir;dp[cur][2]=dp[cur][1]-sec;
}signed main(){//freopen("traffic2.in","r",stdin);//freopen("traffic2.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,u,v;i<=m;i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}int ans=0;for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0),ans+=min({dp[i][0],dp[i][1],dp[i][2]});cout<<ans+n-1-m;return 0;
}

D

待补......

总结

树形 dp:转化为子树内问题分类讨论设状态以及转移.

两个技巧点. 以上.

http://www.hskmm.com/?act=detail&tid=25511

相关文章:

  • 递推求解逆元
  • 一些做题记录(2025 2-3)
  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介
  • 无法定时发送
  • 计算能力的重要性:从内存配置到进程迁移的未来展望
  • MongoDB财报超预期,文档数据库技术解析
  • 深入解析:【RabbitMQ】- Channel和Delivery Tag机制
  • 2020CSPS T1 儒略日题解
  • 调用百度AI接口实现网络图片中的文字识别
  • 英语_阅读_ChatGPT_待读
  • 实用指南:React 组件异常捕获机制详解
  • win11 为什么我的程序断网就转入导后台进程
  • 深入解析:AI与区块链:数据确权与模型共享的未来
  • 10.6阅读笔记
  • hetao 国庆
  • 详细介绍:运维 pgsql 安装完后某次启动不了
  • visual studio
  • [MCP] StreamableHTTPServer
  • 牛客 周赛109 20250924
  • 罗技G102螺丝型号
  • 详细介绍:深入剖析C#构造函数执行:基类调用、初始化顺序与访问控制
  • 英语_阅读_Let your baby go_待读
  • 第三章习题
  • 系统管理员的日常困境与幽默自嘲