hiho刷题日记——第十一天树中的最长路

题目

给出一个无根树（其实就可以之间看作一个特殊的无向图）
求出该无根树的最长路
样例输入
8
1 2
1 3
1 4
4 5
3 6
6 7
7 8
样例输出
6

思路

对于任意一个节点，将其视为根节点，找到深度最深的节点记录下来。
再将找到的节点作为根节点找出深度最深的节点，两点之间的路便是这无根树的最长路。

原因

假设我们已知了最长路的两个端点。那么将这颗无根树上的任意一个节点作为根节点，找到的深度最深的节点都会是这两个节点中的一个。而将这最长路的端点作为根节点，找到的最深的节点，就会是这最长路的另一个端点。

代码

#include<cstdio>
#include<cstring>
using namespace std;

typedef struct{
    int v,next;
}EDGE; 

EDGE edge[100005<<1];
int head[100005];
int e=0,node=0,ans=0;

inline void addEdge(int v,int u)
{
    edge[e].v=v;
    edge[e].next=head[u];
    head[u]=e++;
}

inline void dfs(int cur,int pre,int d)
{
    if(d>ans)
    {
        ans=d;
        node=cur;
    }

    for(int i=head[cur];i!=-1;i=edge[i].next)
        if(edge[i].v!=pre) dfs(edge[i].v,cur,d+1);
}

int main()
{
    memset(head,-1,sizeof head);
    int N;
    int a,b;
    scanf("%d",&N);
    for(int i=1;i<N;i++)
    {
        scanf("%d%d",&a,&b);
        addEdge(a,b);
        addEdge(b,a);
    }

    dfs(1,0,0);
    dfs(node,0,0);
    printf("%d",ans);

    return 0;
}