hdu 3534 树形dp ***

#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int MAXN=;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,len;
}edge[MAXN*];
int head[MAXN];
int tol;
int maxn[MAXN];//该节点往下到叶子结点的最大距离
int smaxn[MAXN];// 次大距离
int maxn_num[MAXN];//最大距离的个数
int smaxn_num[MAXN];//次大距离的个数
int path[MAXN];//该结点为根的子树中，包含该结点的最长路径长度
int num[MAXN];//最长路径的长度 void init()
{
tol=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)
{
edge[tol].to=v;
edge[tol].len=w;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].to=u;
edge[tol].len=w;
edge[tol].next=head[v];
head[v]=tol++;
} void dfs(int u,int pre)
{
maxn[u]=smaxn[u]=;
maxn_num[u]=smaxn_num[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)continue;
dfs(v,u);
if(maxn[v]+edge[i].len>maxn[u])
{
smaxn[u]=maxn[u];
smaxn_num[u]=maxn_num[u];
maxn[u]=maxn[v]+edge[i].len;
maxn_num[u]=maxn_num[v];
}
else if(maxn[v]+edge[i].len==maxn[u])
{
maxn_num[u]+=maxn_num[v];
}
else if(maxn[v]+edge[i].len>smaxn[u])
{
smaxn[u]=maxn[v]+edge[i].len;
smaxn_num[u]=maxn_num[v];
}
else if(maxn[v]+edge[i].len==smaxn[u])
{
smaxn_num[u]+=maxn_num[v];
}
}
if(maxn_num[u]==)//叶子结点
{
maxn[u]=smaxn[u]=;
maxn_num[u]=smaxn_num[u]=;
path[u]=;
num[u]=;
return;
}
//到这里已经统计出了u节点到叶子的最长和次长
int c1=,c2=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)continue;
if(maxn[u]==maxn[v]+edge[i].len)c1++;
else if(smaxn[u]==maxn[v]+edge[i].len)c2++;
}
path[u]=;
num[u]=;
if(c1>=)//最长+最长
{
int tmp=;
path[u]=maxn[u]*;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)continue;
if(maxn[u]==maxn[v]+edge[i].len)
{
num[u]+=tmp*maxn_num[v];
tmp+=maxn_num[v];
}
}
}
else if(c1>= && c2>=)//最长+次长
{
path[u]=maxn[u]+smaxn[u];
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)continue;
if(maxn[u]==maxn[v]+edge[i].len)
{
num[u]+=maxn_num[v]*smaxn_num[u];
}
}
}
else//最长
{
path[u]=maxn[u];
num[u]=maxn_num[u];
}
}
int main()
{
int n;
while(scanf("%d",&n)==)
{
int u,v,w;
init();
for(int i=;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dfs(,-);
int ans1=,ans2=;
for(int i=;i<=n;i++)
{
if(path[i]>ans1)
{
ans1=path[i];
ans2=num[i];
}
else if(path[i]==ans1)
ans2+=num[i];
}
printf("%d %d\n",ans1,ans2);
}
return ;
}