hdoj2196——两次树形dp(下->上、上->下)

开始想的太简单,以为到树中某点的距离最远的点只有两种情况:1.在以该点为根的子树的某个叶节点。2.从该点往上经过根结点,在从根结点到最远结点。
而事实上,看了网上的解题报告才发现,从某点往上的最远距离不一定经过根结点,但一定经过父节点。
dp[i].first表示以i点为根的子树中到点i的最远距离
dp[i].second表示以i点为根的子树中到点i的次远距离
dp[i].sonid表示对应于dp[i].first的i的那个儿子编号
(注意:上面的second指的是不和dp[i].first经过i的同一个儿子节点的最远距离)
dp2[i]表示经过i点的父亲的最远距离
这样两次dfs即可。第一次从下往上更新dp,第二次从上往下更新dp2(由于是从上往下更新,所以求解dp2[i->son]时用到的dp2[i]已经正确求解出来了,这样就保证了正确性)。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Edge{
	int to;
	int len;
	int next;
}Edge;
Edge edge[10010];
int head[10010],num[10010];
typedef struct DP{
	int first;
	int second;
	int sonid;
}DP;
DP dp[10010];
int dp2[10010];
int max(int a,int b)
{
	return a>b?a:b;
}
void dfs(int cur)
{
	int i,d=num[cur];
	if(d==0)
	{
		return;
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		dfs(son);
		if(dp[son].first+edge[i].len>dp[cur].first)
		{
			dp[cur].first=dp[son].first+edge[i].len;
			dp[cur].sonid=son;
		}
		
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		if(son!=dp[cur].sonid)
		{
			if(dp[son].first+edge[i].len>dp[cur].second)
				dp[cur].second=dp[son].first+edge[i].len;
		}
	
	}
	return;
}
void dfs2(int cur,int fa,int len)
{
	int i;
	if(fa!=-1)
	{
		if(cur!=dp[fa].sonid)
		{
			dp2[cur]=max(dp[fa].first,dp2[fa])+len;
		
		}
		else
		{
			dp2[cur]=max(dp[fa].second,dp2[fa])+len;
		}
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		dfs2(son,cur,edge[i].len);
		
	}
	return;
}
int main()
{
	int n;
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			continue;
		if(n==1)
		{
			printf("0\n");
			continue;
		}
		memset(head,-1,sizeof(head));
		memset(num,0,sizeof(num));
		memset(dp2,0,sizeof(dp2));
		for(i=1;i<=n;i++)
		{
			dp[i].first=0;
			dp[i].second=0;
			dp[i].sonid=0;
		}
		int cnt=0;
		for(i=2;i<=n;i++)
		{
			int fa,len;
			scanf("%d %d",&fa,&len);
			edge[cnt].len=len;
			edge[cnt].to=i;
			edge[cnt].next=head[fa];
			head[fa]=cnt++;
			num[fa]++;
		}
		dfs(1);
		dfs2(1,-1,0);
		for(i=1;i<=n;i++)
		{
			printf("%d\n",max(dp[i].first,dp2[i]));
		}
			


	}
//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>