hihocoder #1224 : 赛车 dfs

#1224 : 赛车

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://hihocoder.com/problemset/problem/1224

Description

幻想乡有一个赛车场。赛车场里有N个地点。同时地点之间还有单向的道路存在。

这些道路使得赛车场形成了一个外向树的结构。也就是说，道路将这N个地点连成了一个有根树。并且所有的边都是从父亲指向孩子的。

由于幽香喜欢刺激，每次她去赛车场都会从根节点出发，选择最长的一条路径来玩。

但是现在幽香感觉最长的路径还是太短了，她打算在赛车场里新建一条道路使得新的最长路径最长。

同时，如果道路形成了一个环，那么可能会出现交通事故，所以幽香新建的道路不能导致环的出现。

你能帮幽香算出新建一条道路后的最长路径吗？幽香知道根节点一定是1号点。

Input

一行一个数N，表示地点的数量。

接下来N-1行，每行两个数a和b，表示从点a到点b有一条单向路径。所有点从1到n标号。

数据范围：

n<=100000。

Output

一行表示新建一条边后的最长路径。

Sample Input

5
1 2
2 3
1 4
4 5

Sample Output

HINT

题意

题解：

http://media.hihocoder.com/contests/challenge14/hihoCoder-Challenge14-Solution.pdf

官方题解在上面

首先我们先dfs出最长链，然后我们正在dfs出每一个点能够最长延展多少

然后最后答案就是最长链的长度+最长延展多少就好了

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 120051
#define mod 10007
#define eps 1e-9
int Num;
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=~0u>>1;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************

vector<int> E[maxn];
int fa[maxn];
int dep[maxn];
int key[maxn];
void dfs(int x,int deep)
{
    dep[x]=deep;
    for(int i=0;i<E[x].size();i++)
    {
        int v=E[x][i];
        if(key[v])
            continue;
        fa[v]=x;
        dfs(v,deep+1);
    }
}
int main()
{
    int n=read();
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read();
        E[a].push_back(b);
    }
    dfs(1,1);
    int mx=0,bj;
    for(int i=1;i<=n;i++)
    {
        if(dep[i]>mx)
        {
            mx=dep[i];
            bj=i;
        }
    }//找到最长链
    int ans=mx;
    int x = bj;
    while(x!=1)
    {
        key[x]=1;
        x=fa[x];
    }
    key[1]=1;
    for(int i=0;i<=n;i++)
    {
        if(key[i])
        {
            dfs(i,0);
        }
    }
    mx = 0;
    for(int i=1;i<=n;i++)
    {
        if(!key[i])
            mx = max(mx,dep[i]);
    }
    ans = max(0,ans+mx-1);
    printf("%d
",ans);
    return 0;
}