Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 31049 Accepted Submission(s): 3929
Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
#define PI acos(-1.0)
#define eps 1e-8
typedef long long ll;
typedef pair<int,int > P;
const int N=1e5+,M=1e5+;
const int inf=0x3f3f3f3f;
const ll INF=1e18+,mod=1e9+;
struct edge
{
int from,to;
ll w;
int next;
};
edge es[M];
int cnt,head[N];
ll dp[N][];
void init()
{
cnt=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,ll w)
{
cnt++;
es[cnt].from=u,es[cnt].to=v;
es[cnt].w=w;
es[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int fa)
{
for(int i=head[u]; i!=-; i=es[i].next)
{
edge e=es[i];
if(e.to==fa) continue;
dfs1(e.to,u);
ll d=dp[e.to][]+e.w;
if(d>dp[u][]) swap(d,dp[u][]);
if(d>dp[u][]) swap(d,dp[u][]);
}
}
void dfs2(int u,int fa)
{
for(int i=head[u]; i!=-; i=es[i].next)
{
edge e=es[i];
if(e.to==fa) continue;
if(dp[u][]==dp[e.to][]+e.w)
dp[e.to][]=max(dp[u][],dp[u][])+e.w;
else
dp[e.to][]=max(dp[u][],dp[u][])+e.w;
dfs2(e.to,u);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
init();
for(int i=,j; i<=n; i++)
{
ll w;
scanf("%d%lld",&j,&w);
addedge(i,j,w);
addedge(j,i,w);
}
memset(dp,,sizeof(dp));
dfs1(,);
dfs2(,);
for(int i=; i<=n; i++)
printf("%d\n",max(dp[i][],dp[i][]));
}
return ;
}
树形dp
HDU 2196.Computer 树形dp 树的直径的更多相关文章
-
HDU 2196 Computer 树形DP经典题
链接:http://acm.hdu.edu.cn/showproblem.php? pid=2196 题意:每一个电脑都用线连接到了还有一台电脑,连接用的线有一定的长度,最后把全部电脑连成了一棵树,问 ...
-
computer(树形dp || 树的直径)
Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
HDU 2196 Computer 树形DP 经典题
给出一棵树,边有权值,求出离每一个节点最远的点的距离 树形DP,经典题 本来这道题是无根树,可以随意选择root, 但是根据输入数据的方式,选择root=1明显可以方便很多. 我们先把边权转化为点权, ...
-
hdu-2169 Computer(树形dp+树的直径)
题目链接: Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) ...
-
hdu 2196 Computer(树形DP)
Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
hdu 2196 Computer 树形dp模板题
Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total S ...
-
hdu 2196 Computer(树形DP经典)
Computer Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
Computer(HDU2196+树形dp+树的直径)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196 题目: 题意:有n台电脑,每台电脑连接其他电脑,第i行(包括第一行的n)连接u,长度为w,问你每 ...
-
hdu 4607 树形dp 树的直径
题目大意:给你n个点,n-1条边,将图连成一棵生成树,问你从任意点为起点,走k(k<=n)个点,至少需要走多少距离(每条边的距离是1): 思路:树形dp求树的直径r: a:若k<=r+1 ...
随机推荐
-
.NET工程师面试宝典
.Net工程师面试笔试宝典 传智播客.Net培训班内部资料 这套面试笔试宝典是传智播客在多年的教学和学生就业指导过程中积累下来的宝贵资料,大部分来自于学员从面试现场带过来的真实笔试面试题,覆盖了主流的 ...
-
【OpenStack】OpenStack系列2之KeyStone详解
源码下载.依赖安装 参考:http://www.oschina.net/question/565065_66271 https://github.com/yongluo2013/osf-opensta ...
-
JavaScript中toStirng()与Object.prototype.toString.call()方法浅谈
toStirng()与Object.prototype.toString.call()方法浅谈 一.toString()是一个怎样的方法?它是能将某一个值转化为字符串的方法.然而它是如何将一个值从一种 ...
-
ByteBuffer解析
一.前言 前一篇文章我们介绍了Android中直播视频技术的基础大纲知识,这里就开始一一讲解各个知识点,首先主要来看一下视频直播中的一个重要的基础核心类:ByteBuffer,这个类看上去都知道了,是 ...
-
Galera 10.0.20 on CentOS 6.6
Galera 10.0.20 on CentOS 6.6 0.使用场景 数据库软件:mariadb-galera-10.0.20-linux-x86_64.tar.gz 集群管理:galera-3-2 ...
-
利用python进行数据分析之绘图和可视化
matplotlib API入门 使用matplotlib的办法最常用的方式是pylab的ipython,pylab模式还会向ipython引入一大堆模块和函数提供一种更接近与matlab的界面,ma ...
-
8Manage:“消费升级”缘何剑指企业一体化管理变革?
[导读]提到消费升级,大家都会想起美学.个性化.品质等标签,近年来经济发展所伴随的消费需求转型在逐渐凸显,开始从粗狂型到精细化,如:关注产品性价比.服务个性化等内容.企业在消费升级下应该如何应对呢?8 ...
-
logrotate异常排查
[root@dev240 logrotate.d]# /usr/sbin/logrotate -v /etc/logrotate.conf reading config file /etc/logro ...
-
python functiontools模块中的 wraps
直接上代码看效果: # 定义一个最简单的装饰器 def user_login_data(f): def wrapper(*args, **kwargs): return f(*args, **kwar ...
-
c#构造初使化的顺序
这个很基础的知识,但我至今才意识到它.想想也很失败. 直接上代码:很简单 public class Base { ; public Base() { System.Console.WriteLine( ...