洛谷 1131 [ZJOI2007]时态同步——树形dp
2024-08-29 17:15:45
题目: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 ;
}
最新文章
- Python2 下 Unicode 的一个小bug
- Spring JdbcTemplate 调用存储过程
- Convert Geometry data into a Geography data in MS SQL Server
- 自设chrome默认滚动条样式
- kubernetes kubeadm部署高可用集群
- 1247 排排站 USACO(查分+hash)
- ubuntu 下 github 使用方法 以及异常修改
- Android窗口管理服务WindowManagerService对壁纸窗口(Wallpaper Window)的管理分析
- SQL中with(nolock)作用说明
- node使用消息队列RabbitMQ一
- jquery常用函数
- Webpack vs Browersify vs SystemJs for SPAs
- 吐槽一下--最近多次在腾讯以及万科的面试经历---Web前端与PHP后端开发
- Win7 系统记事本乱码及cmd闪退解决办法
- hover如何在移动浏览器上触发
- PHP变量传值赋值和引用赋值,变量销毁
- 20165223 《信息安全系统设计基础》 实现mypwd
- 分享一个mac for redis-desktop-manager破解版安装包
- 接口转换 数据库列表的内容 显示在datagrid
- linux 硬盘挂载
热门文章
- HTML元素定位
- 给定一个递增序列,a1 <;a2 <;...<;an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<;n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少?
- XJTU Summer Holiday Test 1(Divisibility by Eight-8的倍数)
- PowerBuilder -- 数字金额大写
- 【BZOJ3319】黑白树 并查集
- Python 字符串操作(截取/替换/查找/分割)
- WebApi 传参详解(转)
- coreseek中文搜索
- Android实现下拉导航选择菜单效果
- <;raspberry pi >; 用树莓派来听落网电台