树的直径

给n个点和m条边，边的权值为1，求树的直径.

HihoCoder - 1050 树中的最长路(树的直径,dfs)

这道题有两种做法，第一中是官方做法，也就是这个题目中讲的做法，枚举每一个点作为转折点t，求出以t为根节点的子树中的‘最长路’以及与‘最长路’不重合的‘次长路’，用这两条路的长度之和去更新答案，那么最终的答案就是这棵树的最长路长度

另一种是做法就是找一个点开始dfs，然后找到一个最远的点，然后以这个点为根，再进行一遍dfs，然后以这个点求出的最长的长度就是最长路。

代码

官方解法

const int N=1e5+20;
int n;
int first[N],tot,ans;
struct edge
{
    int v,next;
} e[N*2];
void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}
void init()
{
    mem(first,-1);
    tot=0;
    ans=0;
}
int dfs(int u,int fa)
{
    int fir=0,sec=0,depth;
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa)
        {
            depth=dfs(v,u)+1;
            if(depth>fir)
            {
                sec=fir;
                fir=depth;
            }
            else if(depth>sec)
                sec=depth;
        }
    }
    ans=max(ans,fir+sec);
    return fir;
}
int main()
{
    int u,v;
    init();
    scanf("%d",&n);
    for(int i=1; i<=n-1; i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

搜索解法

const int N=1e5+20;
int n;
int first[N],tot,maxdepth,root;
struct edge
{
    int v,next;
} e[N*2];
void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}
void init()
{
    mem(first,-1);
    tot=0;
    maxdepth=0;
    root=0;
}
void dfs(int depth,int u,int fa)
{
    if(depth>maxdepth)
    {
        maxdepth=depth;
        root=u;
    }
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa)
            dfs(depth+1,v,u);
    }
}

int main()
{
    int u,v;
    init();
    scanf("%d",&n);
    for(int i=1; i<=n-1; i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(0,1,0);
    maxdepth=0;
    dfs(0,root,0);
    printf("%d\n",maxdepth);
    return 0;
}