题目:https://www.luogu.org/problemnew/show/P1131

因为越高,调节一个影响到的越多,所以底下只要把子树间的差异消除了就行了,与其他部分的差异由更高的边调节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+;
int n,rt,hd[N],xnt,to[N<<],nxt[N<<],w[N<<];
ll ans,dis[N<<];
int rdn()
{
int ret=,fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=; ch=getchar();}
while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return fx?ret:-ret;
}
void add(int x,int y,int z)
{
to[++xnt]=y; nxt[xnt]=hd[x]; hd[x]=xnt; w[xnt]=z;
to[++xnt]=x; nxt[xnt]=hd[y]; hd[y]=xnt; w[xnt]=z;
}
void dfs(int cr,int fa)
{
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa)
{
dfs(v,cr);
dis[cr]=max(dis[cr],dis[v]+w[i]);
}
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa)
ans+=dis[cr]-(dis[v]+w[i]);
}
int main()
{
n=rdn(); rt=rdn();
for(int i=,u,v,z;i<n;i++)
{
u=rdn(); v=rdn(); z=rdn(); add(u,v,z);
}
dfs(rt,);
printf("%lld\n",ans);
return ;
}

最新文章

  1. Python2 下 Unicode 的一个小bug
  2. Spring JdbcTemplate 调用存储过程
  3. Convert Geometry data into a Geography data in MS SQL Server
  4. 自设chrome默认滚动条样式
  5. kubernetes kubeadm部署高可用集群
  6. 1247 排排站 USACO(查分+hash)
  7. ubuntu 下 github 使用方法 以及异常修改
  8. Android窗口管理服务WindowManagerService对壁纸窗口(Wallpaper Window)的管理分析
  9. SQL中with(nolock)作用说明
  10. node使用消息队列RabbitMQ一
  11. jquery常用函数
  12. Webpack vs Browersify vs SystemJs for SPAs
  13. 吐槽一下--最近多次在腾讯以及万科的面试经历---Web前端与PHP后端开发
  14. Win7 系统记事本乱码及cmd闪退解决办法
  15. hover如何在移动浏览器上触发
  16. PHP变量传值赋值和引用赋值,变量销毁
  17. 20165223 《信息安全系统设计基础》 实现mypwd
  18. 分享一个mac for redis-desktop-manager破解版安装包
  19. 接口转换 数据库列表的内容 显示在datagrid
  20. linux 硬盘挂载

热门文章

  1. HTML元素定位
  2. 给定一个递增序列,a1 &lt;a2 &lt;...&lt;an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i&lt;n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少?
  3. XJTU Summer Holiday Test 1(Divisibility by Eight-8的倍数)
  4. PowerBuilder -- 数字金额大写
  5. 【BZOJ3319】黑白树 并查集
  6. Python 字符串操作(截取/替换/查找/分割)
  7. WebApi 传参详解(转)
  8. coreseek中文搜索
  9. Android实现下拉导航选择菜单效果
  10. &lt;raspberry pi &gt; 用树莓派来听落网电台