hihoCoder挑战赛14 题目2 : 赛车树的性质

本文主要是介绍hihoCoder挑战赛14 题目2 : 赛车树的性质，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目2 : 赛车

时间限制: 20000ms

单点时限: 1000ms

内存限制: 256MB

描述

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

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

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

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

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

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

输入

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

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

数据范围：

n<=100000。

输出

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

样例输入

样例输出

题意。给出一个有向树根为1，要求加一条边后，所能形成的从1出发的最长路，不能形成环。

用深搜找出每个结占作为根时的最长路，结果就以1为起点的最长路，加上不在这条路上的其它点的最长路的和加上1就是答案了。

#define N 100050
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,s,e,num[N][2],goal[N][2];
bool vis[N];
vector<int> p[N];
void DFS(int x){num[x][0] = num[x][1] = 0;goal[x][0] = goal[x][1] = x;FI(p[x].size()){int g = p[x][i];DFS(g);if(num[g][0] + 1 > num[x][0]){num[x][0] = num[g][0] + 1;goal[x][0] = g;}}
}
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);while(S(n)!=EOF){FI(n+1) p[i].clear();fill(vis,false);FI(n-1){scan_d(s);scan_d(e);p[s].push_back(e);}DFS(1);int start = 1;vis[start] = true;while(goal[start][0] != start){start = goal[start][0];vis[start] = true;}int ans = num[1][0],temp = -1;For(i,1,n+1){if(!vis[i]){temp = max(temp,num[i][0]);}}if(temp == -1)printf("0\n");elseprintf("%d\n",ans+temp + 1);}//fclose(stdin);//fclose(stdout);return 0;
}

这篇关于hihoCoder挑战赛14 题目2 : 赛车树的性质的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！