hdu 3534 Tree(树形DP)

题目链接：hdu 3534 Tree

题意：

给你一棵n个节点,n-1条边的树，每条边有一个长度，现在问你最长的边的长度为多少，有多少条。

题解：

其实这种题不用记录最长和次长，我们开两个数组，len[i]，num[i]。

表示以i为根结点出发的最长的长度以及最长的边的条数。

然后我们只需要一个dfs，先用子节点的信息来更新答案，然后在更新当前节点的len和num记录的信息。

这样就不用记录最长和次长。

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;

const int N=1e4+7;

int g[N],v[N*2],nxt[N*2],w[N*2],ed;
int n,ans,k,len[N],num[N];

void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}

void dfs(int x,int fa)
{
    len[x]=0,num[x]=1;
    for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
    {
        dfs(v[i],x);
        int tmp=w[i]+len[v[i]];
        if(tmp+len[x]>ans)ans=tmp+len[x],k=num[x]*num[v[i]];
        else if(tmp+len[x]==ans)k+=num[x]*num[v[i]];
        if(tmp>len[x])len[x]=tmp,num[x]=num[v[i]];
        else if(tmp==len[x])num[x]+=num[v[i]];
    }
}

int main(){
    while(~scanf("%d",&n))
    {
        mst(g,0),ed=0;
        int x,y,z;
        F(i,1,n-1)
        {
            scanf("%d%d%d",&x,&y,&z);
            adg(x,y,z),adg(y,x,z);
        }
        ans=-INT_MAX,k=0;
        dfs(1,0),printf("%d %d
",ans,k);
    }
    return 0;
}