HDU 2196.Computer 树形dp 树的直径

时间:2023-01-18 08:16:21

Computer

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 31049    Accepted Submission(s): 3929

Problem Description
A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information. 
HDU 2196.Computer 树形dp 树的直径

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.

 
Input
Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
 
Output
For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).
 
Sample Input
5
1 1
2 1
3 1
1 1
 
Sample Output
3
2
3
4
4
 
Author
scnu
 
题意:求一棵树上任一点到其他点的最远距离。
思路:1)树上的任意一点到其他点的最远距离必然是到达树的直径的两个端点之一,树的直径只需要2遍dfs即可。
2)重点说一下树形dp的思路。dp[i][0],dp[i][1],dp[i][2]分别表示:i通过子树可以达到的最远距离;i通过子树可以到达的次远距离(不同儿子);i通过父亲能够到达的最远距离。那么ans[i]=max(dp[i][0],dp[i][2]);
对于<u,v>w:
状态转移方程:dp[u][0]=dp[v][0]+w;dp[u][1]也是这样得到,但是注意dp[i][1]是通过另外的儿子获得。
1.dp[v][2]=dp[u][1]+w; 2.dp[v][2]=dp[u][0]+w;当<u,v> 是u的最长子树的路径时,只能用1式子。
代码:
#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 树的直径的更多相关文章

  1. HDU 2196 Computer 树形DP经典题

    链接:http://acm.hdu.edu.cn/showproblem.php? pid=2196 题意:每一个电脑都用线连接到了还有一台电脑,连接用的线有一定的长度,最后把全部电脑连成了一棵树,问 ...

  2. computer&lpar;树形dp &vert;&vert; 树的直径&rpar;

    Computer Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Su ...

  3. HDU 2196 Computer 树形DP 经典题

    给出一棵树,边有权值,求出离每一个节点最远的点的距离 树形DP,经典题 本来这道题是无根树,可以随意选择root, 但是根据输入数据的方式,选择root=1明显可以方便很多. 我们先把边权转化为点权, ...

  4. hdu-2169 Computer&lpar;树形dp&plus;树的直径&rpar;

    题目链接: Computer Time Limit: 1000/1000 MS (Java/Others)     Memory Limit: 32768/32768 K (Java/Others) ...

  5. hdu 2196 Computer&lpar;树形DP&rpar;

    Computer Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Su ...

  6. hdu 2196 Computer 树形dp模板题

    Computer Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total S ...

  7. hdu 2196 Computer&lpar;树形DP经典&rpar;

    Computer Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Su ...

  8. Computer(HDU2196&plus;树形dp&plus;树的直径)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196 题目: 题意:有n台电脑,每台电脑连接其他电脑,第i行(包括第一行的n)连接u,长度为w,问你每 ...

  9. hdu 4607 树形dp 树的直径

    题目大意:给你n个点,n-1条边,将图连成一棵生成树,问你从任意点为起点,走k(k<=n)个点,至少需要走多少距离(每条边的距离是1): 思路:树形dp求树的直径r: a:若k<=r+1 ...

随机推荐

  1. &period;NET工程师面试宝典

    .Net工程师面试笔试宝典 传智播客.Net培训班内部资料 这套面试笔试宝典是传智播客在多年的教学和学生就业指导过程中积累下来的宝贵资料,大部分来自于学员从面试现场带过来的真实笔试面试题,覆盖了主流的 ...

  2. 【OpenStack】OpenStack系列2之KeyStone详解

    源码下载.依赖安装 参考:http://www.oschina.net/question/565065_66271 https://github.com/yongluo2013/osf-opensta ...

  3. JavaScript中toStirng&lpar;&rpar;与Object&period;prototype&period;toString&period;call&lpar;&rpar;方法浅谈

    toStirng()与Object.prototype.toString.call()方法浅谈 一.toString()是一个怎样的方法?它是能将某一个值转化为字符串的方法.然而它是如何将一个值从一种 ...

  4. ByteBuffer解析

    一.前言 前一篇文章我们介绍了Android中直播视频技术的基础大纲知识,这里就开始一一讲解各个知识点,首先主要来看一下视频直播中的一个重要的基础核心类:ByteBuffer,这个类看上去都知道了,是 ...

  5. Galera 10&period;0&period;20 on CentOS 6&period;6

    Galera 10.0.20 on CentOS 6.6 0.使用场景 数据库软件:mariadb-galera-10.0.20-linux-x86_64.tar.gz 集群管理:galera-3-2 ...

  6. 利用python进行数据分析之绘图和可视化

    matplotlib API入门 使用matplotlib的办法最常用的方式是pylab的ipython,pylab模式还会向ipython引入一大堆模块和函数提供一种更接近与matlab的界面,ma ...

  7. 8Manage:&OpenCurlyDoubleQuote;消费升级”缘何剑指企业一体化管理变革?

    [导读]提到消费升级,大家都会想起美学.个性化.品质等标签,近年来经济发展所伴随的消费需求转型在逐渐凸显,开始从粗狂型到精细化,如:关注产品性价比.服务个性化等内容.企业在消费升级下应该如何应对呢?8 ...

  8. logrotate异常排查

    [root@dev240 logrotate.d]# /usr/sbin/logrotate -v /etc/logrotate.conf reading config file /etc/logro ...

  9. python functiontools模块中的 wraps

    直接上代码看效果: # 定义一个最简单的装饰器 def user_login_data(f): def wrapper(*args, **kwargs): return f(*args, **kwar ...

  10. c&num;构造初使化的顺序

    这个很基础的知识,但我至今才意识到它.想想也很失败. 直接上代码:很简单 public class Base { ; public Base() { System.Console.WriteLine( ...