树的直径

地点

解释 :
求树的最长路(树的直径)
首先假设树的最长路的两个叶子节点为v1,v2，那么现有结论，从任意一点u出发走到的最远的点一定是（v1,v2）中的一点，然后
再从v1或者v2出发走到的最远点一定是v2或者v1。所以经过两次搜索就能找到最长路径.

相关证明
AC代码:
dfs 找节点

#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);    //找到叶子结点之一,也许是最远.
    CLR(vis);
    dfs(root,0);    //以一个叶子结点开始搜素,则搜出来的长度一定是最长.
    printf("%d\n",max_len);    //输出长度.
}

下面有一道这道题的加强版. (这道题读懂了的话还是可以敲的,就是我读题老是喜欢去抠字眼,其实不太懂时想想另一种说法, 问问自己这种说法是不是也可以符合题目的意思.所以真的要灵活点啊!!!,所以那次比塞真的是我的锅.)
地址

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];  //无向边, 所以需要开大两倍.

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)   //搜素这棵树的直径.
{
    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);   //以任意一个点去搜索, 搜出来最远的那个点一定是直径中的其中一个点.
        int S=0,T=0;
        ll maxx=0;
        for(int i=1;i<=n;i++){
            if(dis1[i]>maxx){
                maxx=dis1[i];
                S=i;   //其中一个点.
            }
        }
        CLR(vis);
        dfs(S,0,dis1);  //在以这个点去搜索, 最远的那个点就是直径中的另一个点.
        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]);   //剩余每个点都选择里其本身比较远的那个点.
        }
        printf("%I64d\n",res);
    }
}

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