hdu3534 树形dp（求树中两点之间的最大距离）

http://acm.hdu.edu.cn/showproblem.php?pid=3534

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

150 2
200 1

/**
hdu 3534  树形dp
题目大意：求给定的树中两点之间的最大长度和这种路的条数
解题思路：首先统计出结点到叶子结点的最长距离和次长距离。然后找寻经过这个点的，
           在这个为根结点的子树中的最长路径个数目。
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;

struct note
{
    int v,w,next;
} edge[maxn*2];

int head[maxn],ip;
int n;
int maxx[maxn];///该节点往下到叶子结点的最大距离
int smaxx[maxn];/// 次大距离
int num_maxx[maxn];///最大距离的个数
int num_smaxx[maxn];///次大距离的个数
int path[maxn];///该结点为根的子树中，包含该结点的最长路径长度
int num[maxn];///最长路径的个数

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

void addedge(int u,int v,int w)
{
    edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++;
}

void dfs(int u,int pre)
{
    maxx[u]=smaxx[u]=0;
    num_maxx[u]=num_smaxx[u]=0;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(v==pre)continue;
        dfs(v,u);
        if(maxx[v]+w>maxx[u])
        {
            smaxx[u]=maxx[u];///随之更新次长信息
            num_smaxx[u]=num_maxx[u];
            maxx[u]=maxx[v]+w;
            num_maxx[u]=num_maxx[v];
        }
        else if(maxx[v]+w==maxx[u])
        {
            num_maxx[u]+=num_maxx[v];
        }
        else if(maxx[v]+w>smaxx[u])
        {
            smaxx[u]=maxx[v]+w;
            num_smaxx[u]=num_maxx[v];
        }
        else if(maxx[v]+w==smaxx[u])
        {
            num_smaxx[u]+=num_maxx[v];
        }
    }
    if(num_maxx[u]==0)///叶子节点
    {
        maxx[u]=smaxx[u]=0;
        num_maxx[u]=num_smaxx[u]=1;
        path[u]=0;
        num[u]=1;
        return;
    }
    int c1=0,c2=0;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(v==pre)continue;
        if(maxx[v]+w==maxx[u]) c1++;
        else if(maxx[v]+w==smaxx[u])c2++;
    }
    path[u]=0;
    num[u]=0;
    if(c1>=2)///最长+最长
    {
        int tmp=0;
        path[u]=maxx[u]*2;
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(v==pre)continue;
            if(maxx[u]==maxx[v]+w)
            {
                num[u]+=tmp*num_maxx[v];
                tmp+=num_maxx[v];
            }
        }
    }
    else if(c1==1&&c2>=1)///最长+次长
    {
        path[u]=maxx[u]+smaxx[u];
        for(int i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(v==pre)continue;
            if(maxx[u]==maxx[v]+w)
            {
               num[u]+= num_maxx[v]*num_smaxx[u];
               break;
            }
        }
    }
    else ///最长
    {
        path[u]=maxx[u];
        num[u]=num_maxx[u];
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        for(int i=1; i<n; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        dfs(1,-1);
        int ans1=0,ans2=0;
        for(int i=1;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 0;
}

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

150 2
200 1

hdu3534 树形dp（求树中两点之间的最大距离）

原文：http://blog.csdn.net/lvshubao1314/article/details/43818571