地點(diǎn)

解釋 :
求樹(shù)的最長(zhǎng)路(樹(shù)的直徑)
首先假設(shè)樹(shù)的最長(zhǎng)路的兩個(gè)葉子節(jié)點(diǎn)為v1,v2，那么現(xiàn)有結(jié)論，從任意一點(diǎn)u出發(fā)走到的最遠(yuǎn)的點(diǎn)一定是（v1,v2）中的一點(diǎn)，然后
再?gòu)膙1或者v2出發(fā)走到的最遠(yuǎn)點(diǎn)一定是v2或者v1。所以經(jīng)過(guò)兩次搜索就能找到最長(zhǎng)路徑.

相關(guān)證明
AC代碼:
dfs 找節(jié)點(diǎn)

#include<cstdio>
#include<vector>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e5+5;
int dep[maxn];
int max_len,root,n;
int vis[maxn];
vector<int>ve[maxn];
int dfs(int x,int len)
{
    vis[x]=1;
    if(len >max_len) max_len=len,root=x;
    for(int i=0;i<ve[x].size();i++){
        if(!vis[ve[x][i]]){
            dfs(ve[x][i],len+1);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    max_len=0;
    CLR(vis);
    dfs(1,0);    //找到葉子結(jié)點(diǎn)之一,也許是最遠(yuǎn).
    CLR(vis);
    dfs(root,0);    //以一個(gè)葉子結(jié)點(diǎn)開(kāi)始搜素,則搜出來(lái)的長(zhǎng)度一定是最長(zhǎng).
    printf("%d\n",max_len);    //輸出長(zhǎng)度.
}

下面有一道這道題的加強(qiáng)版. (這道題讀懂了的話還是可以敲的,就是我讀題老是喜歡去摳字眼,其實(shí)不太懂時(shí)想想另一種說(shuō)法, 問(wèn)問(wèn)自己這種說(shuō)法是不是也可以符合題目的意思.所以真的要靈活點(diǎn)啊!!!,所以那次比塞真的是我的鍋.)
地址

AC代碼:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e5+5;
const db eps=1e-6;
const int inf=1e9;
const ll INF=1e15;

struct node
{
    int to,next,w;
}s[maxn*2];  //無(wú)向邊, 所以需要開(kāi)大兩倍.

int head[maxn];
int ans=0;
void add(int u,int to,int w)
{
    s[ans].to=to;
    s[ans].w=w;
    s[ans].next=head[u];
    head[u]=ans++;
}
ll dis1[maxn],dis2[maxn];
int vis[maxn];
void dfs(int x,ll len,ll *dis)   //搜素這棵樹(shù)的直徑.
{
    dis[x]=len;
    vis[x]=1;
    for(int i=head[x];i!=-1;i=s[i].next){
        if(!vis[s[i].to])
            dfs(s[i].to,len+s[i].w,dis);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        CLR(dis1);
        CLR(dis2);
        CLR(s);
        memset(head,-1,sizeof(head));
        ans=0;
        for(int i=0;i<n-1;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);   //加邊.
            add(v,u,w);
        }
        CLR(vis);
        dfs(1,0,dis1);   //以任意一個(gè)點(diǎn)去搜索, 搜出來(lái)最遠(yuǎn)的那個(gè)點(diǎn)一定是直徑中的其中一個(gè)點(diǎn).
        int S=0,T=0;
        ll maxx=0;
        for(int i=1;i<=n;i++){
            if(dis1[i]>maxx){
                maxx=dis1[i];
                S=i;   //其中一個(gè)點(diǎn).
            }
        }
        CLR(vis);
        dfs(S,0,dis1);  //在以這個(gè)點(diǎn)去搜索, 最遠(yuǎn)的那個(gè)點(diǎn)就是直徑中的另一個(gè)點(diǎn).
        maxx=0;
        for(int i=1;i<=n;i++){
            if(dis1[i]>maxx){
                maxx=dis1[i];
                T=i;
            }
        }
        //printf("%d %d\n",S,T);
        CLR(vis);
        dfs(T,0,dis2);
        ll res=dis1[T];   //先連接直徑.
        /*for(int i=1;i<=n;i++){
            printf("%d ",dis1[i]);
        }
        printf("\n");*/
        for(int i=1;i<=n;i++){
            if(i == S || i == T) continue;
            res += max(dis1[i],dis2[i]);   //剩余每個(gè)點(diǎn)都選擇里其本身比較遠(yuǎn)的那個(gè)點(diǎn).
        }
        printf("%I64d\n",res);
    }
}

我居然再一次敗在long long 上面, 下次要用ll是我全部用ll了.!!!