树形dp hdu4514 湫湫系列故事——设计风景线

题目链接：

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

题目意思：

给你一张图，让你判断图中是否有环，如果没环求出最长的路径。

解题思路：

用dfs判断是否有环，再用两次dfs求出树上的最长路了（树的直径）。

这里用到了一个树的性质，从树上的任意节点出发找到的最长路端点一定是该树直径的端点。证明请看这篇：http://www.haogongju.net/art/1384945

代码：

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

struct Inf
{
   int b,v;  //保存另一端点和该边的权值
};

vector<Inf>myv[110000];
int n,m;
int fa[110000];
bool vis[110000],cir;
int flag,ans;

void dfs(int pre,int cur,int sum,int faa)
{
   if(sum>ans)
   {
      ans=sum;
      flag=cur; //记住最远距离的端点
   }
   vis[cur]=true;
   for(int i=0;i<myv[cur].size();i++)
   {
      if(pre==myv[cur][i].b)  //不往回走
         continue;
      if(vis[myv[cur][i].b])  //说明一定有环
      {
         cir=true;
         return ;
      }
      fa[myv[cur][i].b]=faa;  //把该树的所有节点的fa都置为树根
      dfs(cur,myv[cur][i].b,sum+myv[cur][i].v,faa);
   }
   vis[cur]=false;
}

int main()
{
   while(scanf("%d%d",&n,&m)!=EOF)
   {
      for(int i=1;i<=n;i++)
      {
         myv[i].clear();
         fa[i]=0;
      }
      for(int i=1;i<=m;i++)
      {
         int te1,te2,te3;
         struct Inf aa,bb;

         scanf("%d%d%d",&te1,&te2,&te3);
         aa.b=te2,aa.v=te3;
         bb.b=te1,bb.v=te3;

         myv[te1].push_back(aa);
         myv[te2].push_back(bb);

      }
      cir=false;
      ans=0;
      memset(vis,false,sizeof(vis)); //上一个测试样例可能直接跳出来了，对本次有影响，wa了好几次
      for(int i=1;i<=n;i++)
      {
         if(cir)
            break;
         if(!fa[i])  //如果是树根
            dfs(-1,i,0,i);
      }
     // memset(fa,0,sizeof(fa));
      if(cir)
         printf("YES\n");
      else
      {
         int ans0=0;

         for(int i=1;i<=n;i++)
         {
            if(!fa[i]) //如果是树根
            {
               flag=-1;
               ans=0;
               dfs(-1,i,0,i);
               if(flag!=-1)
                  dfs(-1,flag,0,i);
               ans0=max(ans,ans0);
            }
         }
         printf("%d\n",ans0);
      }

   }
   return 0;
}