http://poj.org/problem?id=1985

当初在刘书看过树上最远对，但是依稀记得是dp，而直径是双dfs好像没关系。

今天终于搞懂了，是双dfs的dp

第一遍dfs产生树形图，f,g分别记录i点只考虑到子树内的叶子的最远距离，次远距离

第二遍dfs利用f和g计算出h，表示i点“上面”的子树内的叶子的最远距离，之所以次远也要是因为可能最远的在子树内不在“上面”。

这里有一个问题，dp是有阶段性的，怎么保证计算h的时候需要的数据都已经计算好了？dfs先dfs再更新，保证子点先算玩，dfs1先更新再dfs1，保证父点先算玩。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define maxn 40005#define For(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,k,n) for(int i=n;i>=k;i--)#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define NEG(a) memset(a,-1,sizeof(a));#define FILL(a) memset(a,0x3f,sizeof(a));#define fp freopen("in.txt","r",stdin)struct edge{ int v, w;};int N,M;int f[maxn],g[maxn],h[maxn],longest[maxn];vector
            
             e[maxn];void init(){ For(i,1,N) e[i].clear(); NEG(f);NEG(g);NEG(h);NEG(longest);}int dfs(int root, int pre){ int est = 0, esti=-1, er=0; if(f[root]!=-1) return f[root]; if(e[root].empty()) { //printf("root=%d\n",root); return f[root] = 0; } for(int i=0;i
             
              est){ est = f[e[root][i].v]+e[root][i].w; esti = i; } } } longest[root] = esti; for(int i=0;i
              
               er&&i!=longest[root]){ er = f[e[root][i].v]+e[root][i].w; } } } g[root] = er; return f[root] = est;}void dfs1(int root, int pre){ for(int i=0;i