HDU 2196(树形dp,n 个点的树上最长路)

果树修剪主要是促进生长、提高产量和改善树形 #生活技巧# #园艺技巧# #果树修剪#

Computer

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

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

Sample Output

3 2 3 4 4

::所有电脑连接成树形结构，要求求出每个结点到离该结点最远距离。

如果以每个结点为根结点，进行一次dfs，那就很容易求出那个最远距离。但是如果只是单纯的暴力，时间是不够的，

不过我们可以用DP的思想，避免计算重复的子问题，利用这个剪枝，效率就相当高。

我的实现方法：以每个结点为根结点root，进行一次dfs，用dp保存的是经过某条边能到达的最远距离。

边的保存是双向的，给每条边一个序号。//下面dp[x], x就是边的序号

以上图为例，首先选取任意一结点这里选1，为根结点，进行dfs，然后我们就可以求出经过边2边1..边4….所能到达的最远距离dp[1], d[2]……dp[4]..

然后以2为根结点dfs, 因为经过边4所能到达最远距离dp[4]以知道。。dp[7], dp[2]也知道，那离结点2最远结点的距离等于max(dp[4], dp[7], dp[2]+dis[3]),//dis[3]表示第三条边的长度

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 10020;

int head[maxn], cnt;

struct xx{

int u,v,w;

int nex;

}edge[maxn*2];

int dp[maxn*2];

void init(){

for(int i = 0;i < maxn;i ++)

head[i] = -1;

for(int i = 0;i < maxn * 2;i ++)

dp[i] = 0;

cnt = 0;

}

void add(int u,int v,int w){

edge[cnt].u = u;

edge[cnt].v = v;

edge[cnt].w = w;

edge[cnt].nex = head[u];

head[u] = cnt ++;

}

int dfs(int p,int fa){

int ans = 0;

for(int i = head[p];i != -1;i = edge[i].nex){

int son = edge[i].v;

if(fa == son) continue;

if(!dp[i]) dp[i] = dfs(son,p) + edge[i].w;

ans = max(ans,dp[i]);

}

return ans;

}

int main()

{

int n;

while(~scanf("%d",&n)){

init();

int v,w;

for(int i = 2;i <= n;i ++){

scanf("%d%d",&v,&w);

add(i,v,w); add(v,i,w);

}

for(int i = 1;i <= n;i ++)

printf("%d\n",dfs(i,-1));

}

return 0;

}

转载自:https://www.cnblogs.com/zyx1314/p/3874872.html

网址：HDU 2196(树形dp,n 个点的树上最长路) https://www.yuejiaxmz.com/news/view/944569

相关内容

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（DP多重背包问题）
【动态规划/路径问题】变形「最小路径和」问题 & 常见 DP 空间优化技巧 ...｜刷题打卡
最小生成树
【组合数学 && dp[i][j] = a*dp[i, j
旅游省钱大法：加权最短路径
最优二叉检索树
0、1背包问题（DP）
HDU 2544 最短路 Dijkstra Flyod
题解：二叉树问题
枣树的生长过程

随便看看