题意：给定一棵树，求这棵树直径的长度和所有直径有多少个公共点。

题解：求直径感觉DFS比BFS好写太多，但是大数据本地爆栈OJ却不爆……思路和BFS版的差不多，第一问是个裸题。因为书中任意两点间有且仅有一条路径，所以所有直径的公共点一定是连续的一段。我们从左向右枚举直径上所有点，如果一个点到直径外一点的距离等于到直径左端的距离，那么这个点就是连续的公共点的最左边的一个，同理可找到最右边的一个。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define ll long longconst int MAXN=200000+2;struct Hash{ int u; ll w; Hash *Next; Hash(){} Hash(int _u,ll _w,Hash *_Next):u(_u),w(_w),Next(_Next){}}*Tab[MAXN],Mem[2*MAXN];int N,A,B,T,f[MAXN],cnt;bool Flag[MAXN];ll Ans=-1,D,g[MAXN];void Insert(int u,int v,ll w){ Tab[u]=&(Mem[cnt++]=Hash(v,w,Tab[u]));}void DFS1(int x,int l,ll d){ if(d>D) D=d,T=x; for(Hash *p=Tab[x];p;p=p->Next) if(p->u!=l) f[p->u]=x,g[p->u]=p->w,DFS1(p->u,x,d+p->w);}void DFS2(int x,int l,ll d){ if(d>D) D=d; for(Hash *p=Tab[x];p;p=p->Next) if(p->u!=l && !Flag[p->u]) DFS2(p->u,x,d+p->w);}int main(){ cin >> N; int u,v;ll w; for(int i=1;i
            
             << Ans << endl; Flag[A]=1; for(int i=B;i!=A;i=f[i]) Flag[i]=1; int l=0,r=0;ll d=0; for(int i=B,t;i;i=f[i]){ t=g[i],r++,D=0,DFS2(i,-1,0); if(D==d) l=r; if(D==Ans-d) break; d+=t; } cout << r-l << endl; return 0;}