题目大意:给你一棵树,每条边有边权,要求增加一些边的边权,使得根节点到每个叶子节点的距离相等,求出最少共增加多少边权。

题解:树形$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;
}

  

最新文章

  1. 结对项目:代码复审+PSP
  2. C# MVC ( 将控制器的实体类注册到视图 )
  3. Mac怎么读写NTFS格式?Mac读写NTFS格式硬盘教程
  4. MongoDB csv文件导入导出
  5. node.js NPM 使用
  6. java String.Format详解
  7. C++语言笔记系列之十二——C++的继承
  8. “玲珑杯”ACM比赛 Round #12题解&amp;源码
  9. cucumber学习笔记
  10. prometheus — nginx-vts-exporter
  11. 前端学习-基础部分-css(二)
  12. Winform外包团队 项目案例展示
  13. Log4j配置发邮件功能
  14. html-form
  15. Maven更新后本地仓库jar后缀带有 lastUpdated
  16. lwip lwiperf 方法进行性能测试 4.5MB/S
  17. Ubuntu下的init.d管理update-rc.d
  18. 【转】31个实用的find命令
  19. Spring Security构建Rest服务-0200-搭建项目
  20. 用 GSL 求解超定方程组及矩阵的奇异值分解(SVD) 2

热门文章

  1. 分享一个PC端六格密码输入框写法
  2. 一些android的日常笔记
  3. 终于搞定了cxgrid的多行表头(转终于搞定了cxgrid的多行表头 )
  4. python入门(续)
  5. mysql 时间相关sql , 按天、月、季度、年等条件进行查询
  6. java 上溯造型与下塑造型
  7. Java线程和多线程(九)——死锁
  8. Fiddler 发送post 请求失败
  9. easyui combox 随便不存在的值,清空
  10. golang select 退出结束goroutine