[洛谷P1131][ZJOI2007]时态同步
2024-09-28 14:31:12
题目大意:给你一棵树,每条边有边权,要求增加一些边的边权,使得根节点到每个叶子节点的距离相等,求出最少共增加多少边权。
题解:树形$DP$,对于每个点,如果它到它的子树中的叶子节点距离不同,一定要在这个时候改变,不然就没有机会了。$dfs$,对于每个点求出要修改多少使得它的子树符合条件。
卡点:无
C++ Code:
#include <cstdio>
#include <algorithm>
#define maxn 500010
int head[maxn], cnt;
struct Edge {
int to, nxt, w;
} e[maxn << 1];
inline void add(int a, int b, int c) {
e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
} long long ans[maxn], M[maxn];
void dfs(int u, int fa = 0) {
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) {
dfs(v, u);
M[u] = std::max(M[u], M[v] + e[i].w);
ans[u] += ans[v];
}
}
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa) ans[u] += M[u] - M[v] - e[i].w;
}
} int n, S;
int main() {
scanf("%d", &n);
scanf("%d", &S);
for (int i = 1, a, b, c; i < n; i++) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dfs(S);
printf("%lld\n", ans[S]);
return 0;
}
最新文章
- 结对项目:代码复审+PSP
- C# MVC ( 将控制器的实体类注册到视图 )
- Mac怎么读写NTFS格式?Mac读写NTFS格式硬盘教程
- MongoDB csv文件导入导出
- node.js NPM 使用
- java String.Format详解
- C++语言笔记系列之十二——C++的继承
- “玲珑杯”ACM比赛 Round #12题解&;源码
- cucumber学习笔记
- prometheus — nginx-vts-exporter
- 前端学习-基础部分-css(二)
- Winform外包团队 项目案例展示
- Log4j配置发邮件功能
- html-form
- Maven更新后本地仓库jar后缀带有 lastUpdated
- lwip lwiperf 方法进行性能测试 4.5MB/S
- Ubuntu下的init.d管理update-rc.d
- 【转】31个实用的find命令
- Spring Security构建Rest服务-0200-搭建项目
- 用 GSL 求解超定方程组及矩阵的奇异值分解(SVD) 2