首页 > ACM题库 > HDU-杭电 > HDU 3534-Tree[解题报告]HOJ
2014
11-05

HDU 3534-Tree[解题报告]HOJ

Tree

问题描述 :

In the Data structure class of HEU, the teacher asks one problem: How to find the longest path of one tree and the number of such longest path?

输入:

There are several test cases. The first line of each case contains only one integer N, means there are N nodes in the tree. N-1 lines follow, each line has three integers w,v and len, indicate that there is one edge between node w and v., and the length of the edge is len.

输出:

There are several test cases. The first line of each case contains only one integer N, means there are N nodes in the tree. N-1 lines follow, each line has three integers w,v and len, indicate that there is one edge between node w and v., and the length of the edge is len.

样例输入:

4
1 2 100
2 3 50
2 4 50
4
1 2 100
2 3 50
3 4 50

样例输出:

150 2
200 1

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 10009
#define NEW() &Edge[++Ans]
#define LL long long
struct edge
{
	int v;
	int len;
	edge *next;
}Edge[maxn*10],*adj[maxn];
int Ans;
///////////
int n;
void addedge(int u,int v,int len)
{
	edge *ptr=NEW();
	ptr->v=v;
	ptr->len=len;
	ptr->next=adj[u]->next;
	adj[u]->next=ptr;
}
bool vis[maxn];
int pre[maxn];
LL dp[maxn][2];
LL res[maxn][2];
struct node
{
	int num;
	LL len;
}a[maxn];
bool operator <(const node &elem1,const node &elem2)
{
	return elem1.len>elem2.len;
}
void dfs(int p)
{	
	int v;
	vis[p]=true;
	for(edge *ptr=adj[p]->next;ptr!=NULL;ptr=ptr->next)
	{
		v=ptr->v;
		if(vis[v])
			continue;
		pre[v]=p;
		dfs(v);		
	}	
	dp[p][0]=0;
	dp[p][1]=1;

	int ans=0;
	for(edge *ptr=adj[p]->next;ptr!=NULL;ptr=ptr->next)
	{
		v=ptr->v;
		if(pre[v]!=p)
			continue;
		ans++;
		a[ans].len=dp[v][0]+ptr->len;
		a[ans].num=dp[v][1];
		if(a[ans].len>dp[p][0])
		{
			dp[p][0]=a[ans].len;
			dp[p][1]=a[ans].num;
		}
		else if(a[ans].len==dp[p][0])		
			dp[p][1]+=a[ans].num;
	}
	sort(a+1,a+1+ans);
	if(ans==0)
	{
		res[p][0]=0;
		res[p][1]=1;
	}
	else if(ans==1)
	{
		res[p][0]=a[1].len;
		res[p][1]=a[1].num;
	}
	else		
	{
		if(a[1].len==a[2].len)
		{
			int sum=0;
			for(int i=1;i<=ans&&a[i].len==a[1].len;i++)
				sum+=a[i].num;
			res[p][0]=a[1].len*2;
			res[p][1]=0;
			int tmp=0;
			for(int i=1;i<=ans&&a[i].len==a[1].len;i++)
				tmp+=a[i].num*(sum-a[i].num);
			res[p][1]+=tmp/2;
		}
		else
		{
			int sum=0;
			for(int i=2;i<=ans&&a[i].len==a[2].len;i++)
				sum+=a[i].num;
			res[p][0]=a[1].len+a[2].len;
			res[p][1]=a[1].num*sum;
		}
	}
}
int main()
{
	for(;;)
	{
		if(scanf("%d",&n)==EOF)
			break;
		if(n==1)
			while(1)
				printf("1111111\n");
		Ans=0;
		for(int i=1;i<=n;i++)
		{
			adj[i]=NEW();
			adj[i]->next=NULL;
		}
		int u,v,len;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&u,&v,&len);	
			addedge(u,v,len);
			addedge(v,u,len);
		}
		memset(vis,0,sizeof(vis));
		dfs(1);		
		LL maxv=-1;
		LL sum=0;
		for(int i=1;i<=n;i++)
		{
			if(res[i][0]>maxv)
			{
				maxv=res[i][0];
				sum=res[i][1];
			}
			else if(res[i][0]==maxv)
				sum+=res[i][1];
		}
		cout<<maxv<<" "<<sum<<endl;
	}
	return 0;
}

  1. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.