2026年1月20日
换根 DP 简介
摘要： ​【换根 DP 简介】● 换根 DP 是树形 DP 的一种重要技术，用于解决需要以树中‌不同节点为根‌分别计算答案的问题。其核心思想是在一次动态规划后，通过‌推导出换根时的状态转移公式‌，高效地计算出所有节点作为根时的结果，避免对每个根节点都进行一次 O(n) 的树形DP（那样总复杂度为 O(n²) 阅读全文
posted @ 2026-01-20 21:22 Triwa 阅读(20) 评论(0) 推荐(0)
洛谷 P10962：Computer ← 换根DP
摘要： ​【题目来源】https://www.luogu.com.cn/problem/P10962http://acm.hdu.edu.cn/showproblem.php?pid=2196【题目描述】某学校在一段时间前购买了第一台计算机（因此这台计算机的编号是 1）。在最近几年中，学校又购买了 N-1 阅读全文
posted @ 2026-01-20 21:07 Triwa 阅读(8) 评论(0) 推荐(0)
洛谷 P3478：[POI 2008] STA-Station ← 换根DP
摘要： ​【题目来源】https://www.luogu.com.cn/problem/P3478【题目描述】给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。一个结点的深度之和定义为该节点到根的简单路径上边的数量。【输入格式】第一行有一个整数，表示树的结点个数 n。接下 阅读全文
posted @ 2026-01-20 14:41 Triwa 阅读(17) 评论(0) 推荐(0)