热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU2196Computer

http:acm.hdu.edu.cnshowproblem.php?pid2196树型DP类似树的直径的\(dp\)构造方式\[dp[u][0]表示以u为根的子树中的最长链\\d

http://acm.hdu.edu.cn/showproblem.php?pid=2196


树型DP

类似树的直径的\(dp\)构造方式

\[dp[u][0]表示以u为根的子树中的最长链\\
dp[u][1]表示以u为根的子树中的次长链(可以与最长链相等)\\
up[u]表示从u到非子树的最长链\\
dp数组一个dfs预处理\\
up[u]要么从其父亲的非子树的最长链转移而来,要么从其父亲的其他子节点转移而来
\]

还是比较容易实现的

\(C++ Code:\)

#include
#include
#include
#include
#define N 20005
using namespace std;
int head[N],d1[N],d2[N],nxt[N];
int n,x,y,tot;
int dp[N][2],up[N];
void add(int x,int y,int z)
{
tot++;
d1[tot]=y,d2[tot]=z;
nxt[tot]=head[x],head[x]=tot;
}
void dfs(int u,int f)
{
for (int i=head[u];i;i=nxt[i])
{
int v=d1[i];
int cost=d2[i];
if (v==f)
continue;
dfs(v,u);
if (dp[v][0]+cost>=dp[u][0])
{
dp[u][1]=dp[u][0];
dp[u][0]=dp[v][0]+cost;
} else
dp[u][1]=max(dp[u][1],dp[v][0]+cost);
}
}
void Clear()
{
memset(dp,0,sizeof dp);
memset(up,0,sizeof up);
memset(head,0,sizeof head);
tot=0;
}
void Getans(int u,int f)
{
for (int i=head[u];i;i=nxt[i])
{
int v=d1[i];
int cost=d2[i];
if (v==f)
continue;
if (dp[u][0]==dp[v][0]+cost)
up[v]=max(up[u],dp[u][1])+cost; else
up[v]=max(up[u],dp[u][0])+cost;
Getans(v,u);
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
Clear();
for (int i=2;i<=n;i++)
{
scanf("%d%d",&x,&y);
add(i,x,y);
add(x,i,y);
}
dfs(1,0);
Getans(1,0);
for (int i=1;i<=n;i++)
printf("%d\n",max(up[i],dp[i][0]));
}
return 0;
}


推荐阅读
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • PHP 编程疑难解析与知识点汇总
    本文详细解答了 PHP 编程中的常见问题,并提供了丰富的代码示例和解决方案,帮助开发者更好地理解和应用 PHP 知识。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
author-avatar
本来就是哦
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有