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

【题解】P1131 [ZJOI2007] 时态同步

P1131 [ZJOI2007] 时态同步

题目传送门

题目大意:
给你一棵带边权的树,求出使所有叶节点到根节点的路程相同的最少操作数(每次操作边权加 1 )

STEP 1.

看到这个题目后,我们就可以联想到一棵树了,具体来讲:

\(n\) 个节点只有 \(n-1\) 条边 \(\implies\)
激发器 \(\implies\) 根节点
终止节点 \(\implies\) 叶节点
电流通过导线的时间 \(\implies\) 边权

尝试使用 树形DP 完成。

STEP 2.

\(f(i)\) 表示从第 \(i\) 个节点发出电流,所有 \(i\) 的子树的叶节点到 \(i\) 路程相同的最少需要操作的次数,

\(num(i)\) 表示当从第 \(i\) 个节点发出电流,所有 \(i\) 的子树的叶节点到 \(i\) 路程相同的操作次数达到最少时,从第 \(i\) 个节点到达叶子节点需要的时间。

经过分析可得,\(num(i)\)(所有 \(i\) 的子树的叶节点到 \(i\) 路程相同的操作次数达到最少时,从第 \(i\) 个节点到达叶子节点需要的时间) 就是其孩子的 \(num\) 加上孩子与其的距离的最大值,具体来说:

\(num(i)=\max\limits_{j∈children_i}num(j)+len(j)\)

(这里的 \(len(x)\)\(x\) 到其父节点的距离)

\(f(i)\) 则为其所有子节点的子树里达到时态同步最少需要操作的次数之和 加上到达叶子节点需要的时间减去所有子树的 \(num(j)\) 加上与其子树的距离这两项的和,具体来说:

\(f(i)=\sum\limits_{j∈children_i}dp(j)+\sum\limits_{j∈children_i}num(i)-(num(j)+len(j))\)

(这里的 \(len(x)\)\(x\) 到其父节点的距离)

需要注意的是,这里的 \(num(x)\) 需要先预处理完毕后再求 \(f(x)\)

最后的答案就是 \(f(root)\),这里的 \(root\) 就是激发器(根节点)。

STEP 3.

将视角转向数据范围:

  • 对于 \(40\%\) 的数据,\(1\le N\le 1000\)
  • 对于 \(100\%\) 的数据,\(1\le N\le 5\times 10^5\)
    对于所有的数据,\(1\le t_e\le 10^6\)

显然,由于 \(t_e\le 10^6\) ,存 \(f(x)\)\(num(x)\) 时,需要开 \(\large{long\space long}\)

STEP 4.

个人存图只爱用 vector 了(带边权就用 vector+pair)

代码(凭良心复制)
#include<bits/stdc++.h>
using namespace std;
#define ll long longint n, rt, a, b, t;
vector<pair<int, int>> tr[500005];
ll dp[500005], num[500005];void dfs1(int i, int fa) {num[i] = 0;for(auto it : tr[i]) {int j = it.first;int dis = it.second;if(j == fa) continue;dfs1(j, i);num[i] = max(num[i], num[j] + dis);}
}void dfs2(int i, int fa) {dp[i] = 0;for(auto it : tr[i]) {int j = it.first;int dis = it.second;if(j == fa) continue;dfs2(j, i);dp[i] += dp[j] + (num[i] - (num[j] + dis));}
}int main() {cin >> n >> rt;for(int i = 1; i < n; i++) {cin >> a >> b >> t;tr[a].push_back({b, t});tr[b].push_back({a, t});}dfs1(rt, 0);dfs2(rt, 0);cout << dp[rt];return 0;
}
http://www.hskmm.com/?act=detail&tid=25922

相关文章:

  • LGP9120 [NOIP 2022.5] 密码锁 学习笔记
  • 深入解析:OpenCV CUDA模块图像处理------创建CUDA加速的Canny边缘检测器对象createCannyEdgeDetector()
  • 机器人技术奖学金项目助力STEM教育发展
  • SAP ABAP 事务码 RZ12 里的 Max Number of WPs Used 参数的作用介绍
  • busybox 没有 clear 命令吗
  • 实用指南:Hive SQL 中 BY 系列关键字全解析:从排序、分发到分组的核心用法
  • 经过基于流视频预测的可泛化双手运行基础策略
  • 每个JavaScript开发者都应掌握的33个核心概念
  • 解决Docker存储空间不足问题 - 指南
  • 完整教程:数据结构:递归的种类(Types of Recursion)
  • Nova Premier模型安全评估结果解析
  • Paypal 设置不自动换汇
  • 诺贝尔生理与医学奖颁给这项革命技术,多家中国公司已布局!(附名单)
  • 钱璐璐,唯一通讯发Nature,作者仅2人!
  • 华为员工工资待遇表:
  • 体验mcp服务的开发集成和演示过程 - 智慧园区
  • AI技术全景解析:从架构设计到社会影响
  • 对话系统中零样本与少样本学习技术解析
  • 随手记 | 关于AI最新趋势和未来发展方向探讨
  • 何夜无雨 - Ishar
  • 玩转树莓派屏幕之四:适配tslib增加触屏准确度
  • caddy搭建静态+PHP+伪静态Web服务器
  • 全自动 AI 视频创作与发布工具:LuoGen-agent
  • 静态库.a与.so库文件的生成与使用
  • CF2145D Inversion Value of a Permutation
  • 牛客刷题-Day8
  • Educational Codeforces Round 183 (Rated for Div. 2)
  • 高三闲话 #2
  • D. Inversion Value of a Permutation edu div2
  • 个人博客公告