HDU-2196-树形dp/计算树上固定起点的最长路
2024-08-28 00:12:28
Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32263 Accepted Submission(s): 4472
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.
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
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
2
3
4
4
Author
scnu
给出一棵树,边上有权值,计算树上每个顶点以自己为起点可以走的最长的路径长度。
经典的树dp,这条最长路径可能是向下走也可能是想自己的父亲走来达到,我们先dfs1计算出所有点向下走达到的最长路径和次长路径,并记录走向的是哪个儿子。然后在dfs2里计算向上走的最长路径,与已知的两条作比较选出最优的。
记录次长路径的必要性在于父亲的最长路可能就是走向的当前的节点,这样显然不能走重边,如果我们有父亲的次长路(存在的话),那么一定能沿着父亲回去。
很少写这种,想了一下午总算1A了。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
const int MAXN=;
int fm[MAXN],sm[MAXN];
int fid[MAXN],sid[MAXN];
vector<pii>g[];
int N;
void dfs1(int u,int fa)
{
fm[u]=sm[u]=;
fid[u]=sid[u]=;
for(int i=;i<g[u].size();++i){
int v=g[u][i].first;
int w=g[u][i].second;
if(v==fa) continue;
dfs1(v,u);
if(fm[v]+w>sm[u]){
sm[u]=fm[v]+w;
sid[u]=v;
if(sm[u]>fm[u]){
swap(fm[u],sm[u]);
swap(fid[u],sid[u]);
}
}
}
}
void dfs2(int u,int fa,int w)
{
if(fm[fa]+w>sm[u]&&fid[fa]!=u){
sm[u]=fm[fa]+w;
sid[u]=fa;
if(sm[u]>fm[u]){
swap(fm[u],sm[u]);
swap(fid[u],sid[u]);
}
}
if(sm[fa]+w>sm[u]&&sid[fa]!=u){
sm[u]=sm[fa]+w;
sid[u]=fa;
if(sm[u]>fm[u]){
swap(fm[u],sm[u]);
swap(fid[u],sid[u]);
}
}
for(int i=;i<g[u].size();++i){
int v=g[u][i].first;
int ww=g[u][i].second;
if(v==fa) continue;
dfs2(v,u,ww);
}
}
int main()
{
while(cin>>N){int u,v,w;
for(int i=;i<=N;++i){
scanf("%d%d",&v,&w);
g[i].push_back(mp(v,w));
g[v].push_back(mp(i,w));
}
dfs1(,);
/*for(int i=1;i<=N;++i)
cout<<fm[i]<<' '<<fid[i]<<' '<<sm[i]<<' '<<sid[i]<<endl;*/
dfs2(,,);
for(int i=;i<=N;++i) printf("%d\n",max(fm[i],sm[i]));
for(int i=;i<=N;++i)g[i].clear();
}
return ;
} /*
3 2 1 5
2 3 0 0
1 4 0 0
0 0 0 0
0 0 0 0
*/
最新文章
- MySQL大数据优化
- Android 学习第18课,单元测试
- VideoToolbox硬件编解码H.264视频流错误码
- AngularJS in Action读书笔记6(实战篇)——bug hunting
- ReferenceQueue的使用
- Python:安装mssql模块功能,并实现与sqlserver连接、查询
- Android开发-环境搭建以及HelloWorld
- 说服式设计(persuasive design)的行为模型
- BZOJ 3514: Codechef MARCH14 GERALD07加强版 [LCT 主席树 kruskal]
- nginx截获客户端请求
- Android图表库MPAndroidChart(十三)——简约的底部柱状图
- ROS_Kinetic_27 在ROS中使用Cartographer进行SLAM
- Linux:Debian系统的安装
- css -理解盒模型
- IIS 6 配置
- app的描述-软件的描述
- Hadoop 集群的一些问题
- CSS布局相关概要
- IIS7.5 URL文件名有加号或空格显示404错误的解决办法
- [BZOJ]4650 优秀的拆分(Noi2016)(哈希+二分)