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

P3574 题解 | 贪心,树形 dp

传送门

题意

给出一颗树,根为 1 号节点,点有点权 \(a\),求从根出发一条遍历每条边恰好两次的路径,使得以下式子最小:

\(t_i\) 为第一次到达一个点时走过的路径条数,特别地 \(t_1 = 2 \times n - 2\)(最后回到 1)

\[\min _ {i = 1} ^ n \left ( t_i + a_i \right ) \]

思路

显然是树形 dp,记 \(f_u\)\(u\) 子树内的最小值答案,\(g_u\) 走整个子树一遍后回到 \(u\) 的距离。

\[\begin{align*} f_u &\leftarrow \max \left ( f_u, f_v + g_u + 1 \right ) \\ g_u &\leftarrow g_u + g_v + 2 \end{align*} \]

每遍历一个儿子都执行上述转移。
每次执行时,第一个式子里的 \(g_u\) 表示遍历 \(v\) 以前的所有儿子走一遍再回到 \(u\) 的代价,\(+1\) 则是到 \(v\) 的代价。

于是关键在于遍历儿子的顺序,考虑贪心。考虑通过调整法来推导出最优解的性质。

如,两个儿子 \(v_1, v_2\)。调整前遍历 \(v_1\) 后遍历 \(v_2\)

那么从 \(v_1,v_2\) 都没遍历向都遍历的转移为:

\[f_u \leftarrow \max \left( f_u, g_u + 1 + \max \left( f_{v_1} , g_{v_1} + 2 + f_{v_2}\right)\right) \]

若交换 \(v_1, v_2\)

\[f_u \leftarrow \max \left( f_u, g_u + 1 + \max \left( f_{v_2} , g_{v_2} + 2 + f_{v_1}\right)\right) \]

那么 \(v_1\)\(v_2\) 前面优于 \(v_2\)\(v_1\) 前面(不交换优于交换)的条件为:

\[\max \left( f_{v_1}, g_{v_1} + 2 + f_{v_2}\right) \lt \max \left( f_{v_2}, g_{v_2} + 2 + f_{v_1}\right) \]

注意到:\(g_{v_1} + 2 + f_{v_2} \gt f_{v_2}\),所以,若满足条件,右侧必须是第二个值成为 \(\max\),即:

\[\max \left( f_{v_1}, g_{v_1} + 2 + f_{v_2}\right) \lt g_{v_2} + 2 + f_{v_1} \]

\(f_{v_1} \lt g_{v_2} + 2 + f_{v_1}\) 恒成立,则有用的只有:

\[g_{v_1} + 2 + f_{v_2} \lt g_{v_2} + 2 + f_{v_1} \]

移项得:

\[g_{v_1} - f_{v_1} \lt g_{v_2} - f_{v_2} \]

于是每个 \(u\),将儿子按照 \(g_{v} - f_v\) 从小到大排序,然后转移即可。

代码:

link

const int N = 1e6 + 5;
int n;
int a[N];
vector<int> e[N];
int f[N], g[N];
void dfs(int u, int fa){if(u != 1) f[u] = a[u];vector<int> vec;for(int v : e[u]){if(v == fa) continue;dfs(v, u);vec.push_back(v);}sort(vec.begin(), vec.end(), [](int v1, int v2){return g[v1] - f[v1] < g[v2] - f[v2];});for(int v : vec){chkmx(f[u], g[u] + f[v] + 1);g[u] += g[v] + 2;}
}
void solve_test_case(){n = read();rep(i, 1, n){a[i] = read();}rep(i, 1, n - 1){int u = read(), v = read();e[u].push_back(v);e[v].push_back(u);}dfs(1, 0);write(max(f[1], g[1] + a[1]));
}
http://www.hskmm.com/?act=detail&tid=26028

相关文章:

  • 爱,在行动中生长,我们因爱而变得辽阔——《岛上书店》读后感
  • Ubuntu 下同名文件替换后编译链接到旧内容的现象分析 - 实践
  • Luogu P14007 「florr IO Round 1」查询游戏 题解 [ 蓝 ] [ 交互 ]
  • RK3588和FPGA桥片之间IO电平信号概率性不能通信原因 - 实践
  • 稀缺计算资源如何塑造机器学习优化专家
  • PWN手的成长之路-10-GDOUCTF 2023-Shellcode-短字节shellcode
  • 优雅的合并GIT分支
  • Docker部署
  • 完整教程:Excel to JSON 插件 2.4.0 版本更新
  • Ai元人文:人文逻辑与规则逻辑的统一
  • 《二千年间》在线阅读
  • 蒟蒻的第一篇随笔
  • oppoR9m刷Linux系统: 安装MTK USB VCOM驱动
  • [特殊字符] FFmpeg 学习笔记 - 详解
  • .NET周刊【9月第3期 2025-09-21】
  • 通过实验直观理解神经网络:ReLU网络与几何解释
  • CCPC2023哈尔滨 游记(VP)
  • 2025教练技术行业深度剖析:目标人群、费用与品牌选择
  • 虚拟现实教育终端科技方案——基于EFISH-SCB-RK3588的全场景国产化替代
  • 【OpenGL ES】不用GLSurfaceView,如何渲染图像
  • LGP9871 [NOIP 2023] 天天爱打卡 学习笔记
  • 【OpenGL ES】Windows上OpenGL环境搭建
  • 完整教程:WordPress 6.5版本带来的新功能
  • 微信开发框架/WTAPI框架
  • 2025连接器厂家权威推荐榜:防水/m12防水/m8/防水3芯/防水t型三通/防水线束线缆/防水包胶连接器实力制造与创新技术深度解析
  • [数学 - 正态分布]
  • 状态压缩 DP
  • QGIS开发笔记(四):QgsRasterLayer加载Cesium二维地图的瓦片地图数据到QGIS
  • 学号20232328 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • Withdraw x Failure《一元微积分》讲义习题