Computer

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.

5
1 1
2 1
3 1
1 1

3
2
3
4
4

题意：给定一颗树，求距离每个点的的最远的距离。

解题思路：最远距离来自两部分，一部分是由子节点而来，还有一部分是从父节点而来，两次dfs，一次求出从子节点而来的最大值，次大值，第二次求从父节点而来的，

以前cf一题思路一模一样，研究了好久没看懂，今天终于看懂了。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-3 18:13:04
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=20020;
int dp[maxn][3],head[maxn],tol;
struct node {
	int next,to,val;
}edge[3*maxn];
void add(int u,int v,int w){
	edge[tol].next=head[u];
	edge[tol].to=v;
	edge[tol].val=w;
	head[u]=tol++;
}
void dfs1(int u,int fa){
	int b1=0,b2=0;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		int ret=dp[v][0]+edge[i].val;
		if(ret>=b1){
			b2=b1;
			b1=ret;
		}
		else if(ret>=b2)
			b2=ret;
	}
	dp[u][0]=b1;
	dp[u][1]=b2;
}
void dfs2(int u,int fa){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dp[v][2]=max(dp[u][2],dp[v][0]+edge[i].val==dp[u][0]?dp[u][1]:dp[u][0])+edge[i].val;
		dfs2(v,u);
	}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int i,j,k,m,n;
	 while(~scanf("%d",&n)){
		 memset(head,-1,sizeof(head));tol=0;
		 memset(dp,0,sizeof(dp));
		 for(i=2;i<=n;i++){
			 scanf("%d%d",&j,&k);
			 add(i,j,k);
			 add(j,i,k);
		 }
		 dfs1(1,-1);
		 dfs2(1,-1);
		 for(i=1;i<=n;i++)
			 printf("%d\n",max(dp[i][0],dp[i][2]));
	 }
     return 0;
}

hdu 2196 树形dp经典题目

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18910681