要自下向上调整,尽可能用一个道具修改多个;

搜的时候记录叶节点的最大深度,减一下就好了。

#include<cstdio>
#include<iostream>
#include<cstring>
#define R register int
using namespace std;
struct edge {
int v,w,nxt;
}e[];
int n,cnt,s;
int fir[];
long long ans,mx[];
inline void add(int u,int v,int w) {e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=fir[u],fir[u]=cnt;}
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
void dfs(int u,int fa) {
//cout<<u<<" "<<fa<<endl;
for(R i=fir[u];i;i=e[i].nxt) {
R v=e[i].v;
if(v==fa) continue;
dfs(v,u); mx[u]=max(mx[u],mx[v]+e[i].w);
}
for(R i=fir[u];i;i=e[i].nxt) {
R v=e[i].v;
if(v==fa) continue;
ans+=mx[u]-(mx[v]+e[i].w);
}
}
signed main() {
n=g(),s=g();
for(R i=;i<n;++i){R u=g(),v=g(),w=g(); add(u,v,w),add(v,u,w);}
dfs(s,); printf("%lld\n",ans);
}

2019.04.26

最新文章

  1. HDU3466背包01
  2. Git操作指南(2) —— Git Gui for Windows的建库、克隆(clone)、上传(push)、下载(pull)、合并(转)
  3. Git版本管理:Windows下Git配置与使用指南 Gitlab
  4. 利用css3-animation来制作逐帧动画
  5. swift3.0 构造器、析构方法(3)
  6. AndroidContentProvider ContentResolver和ContentObserver的使用
  7. javascript 闭包理解例子
  8. Linux 复习
  9. MySQL最佳实践
  10. what&#39;s the 灰盒测试
  11. Y7000联想拯救者gtx1050Ti安装cuda9.0
  12. react性能检测与优化
  13. 那些神奇的before和after使用方法
  14. 大文件断点上传 js+php
  15. 基于HttpClient JSONObject与JSONArray的使用
  16. 最新版的Chrome 69.0 设置始终开启flash而不是先询问
  17. tpshop购物网站价格筛选功能的测试用例设计
  18. 安装配置PhoneGap开发环境(二)——使用Cordova取代PhoneGap创建项目
  19. [19/03/27-星期三] 容器_Iterator(迭代器)之遍历容器元素(List/Set/Map)&amp;Collections工具类
  20. Machine Learning笔记整理 ------ (四)线性模型

热门文章

  1. memcache 加载(对象)所遇到的问题。资源
  2. Solidity payable 方法表现
  3. 31.SUM() 函数
  4. 利用 Aspose.Words 组件,在不依赖与 Office 组件的情况下把 Word 文件转换成 HTML 代码。
  5. MVC下的cshtml和aspx页面
  6. UVa 11149 Power of Matrix (矩阵快速幂,倍增法或构造矩阵)
  7. HTML5 Canvas核心技术:图形、动画与游戏开发 PDF扫描版​
  8. [other] 代码量代码复杂度统计-lizard
  9. docker--基本命令
  10. C# LINQ(7)