2014
11-05

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;
int Ans;
///////////
int n;
{
edge *ptr=NEW();
ptr->v=v;
ptr->len=len;
}
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;
{
v=ptr->v;
if(vis[v])
continue;
pre[v]=p;
dfs(v);
}
dp[p][0]=0;
dp[p][1]=1;

int ans=0;
{
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++)
{
}
int u,v,len;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&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.