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
题目大意:
给定n,代表n台电脑,编号为1的是最初始的电脑,下面n-1对数字,分别编号为2~n的电脑相连电脑的编号与长度。
输出n行,求与第i台电脑最远的电脑的距离。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,dp[],pre[];
struct edge
{
int u,v,w,p;///u与v电脑相连,长度w,u对应的上一条边
edge(){}
edge(int u,int v,int w,int p):u(u),v(v),w(w),p(p){}
}e[];
int dfs(int u,int p)
{
int ans=;
for(int i=pre[u];i!=-;i=e[i].p)
{
int v=e[i].v;
if(v==p) continue;
if(!dp[i])///没更新过
dp[i]=dfs(v,u)+e[i].w;
ans=max(ans,dp[i]); }
return ans;
}
int main()
{
while(cin>>n)
{
memset(dp,,sizeof dp);
memset(pre,-,sizeof pre);
int x=;
for(int i=,v,w;i<=n;i++)
{
cin>>v>>w;
e[x]=edge(i,v,w,pre[i]);
pre[i]=x++;
e[x]=edge(v,i,w,pre[v]);
pre[v]=x++;
}
for(int i=;i<=n;i++)
cout<<dfs(i,-)<<'\n';
}
return ;
}
最新文章
- Git 使用juju
- How to get URL parameters with Javascript?
- Android 通用流行框架大全
- HTML文件基本结构
- 移动端页面调试工具——UC浏览器开发者版
- Go在linux下的安装
- 如何学习一个新的PHP框架
- oracle 全文检索技术
- Kinetic使用注意点--blob
- Could not open a connection to your authentication agent
- Redis 集群解决方案比较
- js jqery判断checkbox是否选中,全选,取消全选,反选,选择奇数偶数项
- 用VSCode开发一个基于asp.net core 2.0/sql server linux(docker)/ng5/bs4的项目(2)
- ant 脚本使用技巧
- RDC去省赛玩前の日常训练 Chapter 2
- Java+Selenium向文本框输入内容以后模仿键盘的";ENTRY";
- 2018-2019-2 网络对抗技术 20165308 Exp2 后门原理与实践
- JxBrowser之四:对Http Response Code的处理
- LeetCode 575 Distribute Candies 解题报告
- Luogu P3227 [HNOI2013]切糕