题意：幻想乡有一个赛车场。赛车场里有N个地点。同时地点之间还有单向的道路存在。
这些道路使得赛车场形成了一个外向树的结构。也就是说，道路将这N个地点连成了一个有根树。并且所有的边都是从父亲指向孩子的。
由于幽香喜欢刺激，每次她去赛车场都会从根节点出发，选择最长的一条路径来玩。
但是现在幽香感觉最长的路径还是太短了，她打算在赛车场里新建一条道路使得新的最长路径最长。
同时，如果道路形成了一个环，那么可能会出现交通事故，所以幽香新建的道路不能导致环的出现。
你能帮幽香算出新建一条道路后的最长路径吗？幽香知道根节点一定是1号点。
先求出最远的那个点，当然那个点肯定是叶子节点，然后再枚举其他叶子节点，计算从那个点到这个叶子节点能走的距离，要计算那个叶子节点和当前叶子节点的LCA，然后计算下距离加起来就行了。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=100000+1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN<<1];
int head[MAXN],tot;
int fa[MAXN][22],dis[MAXN],d[MAXN];
void init(){
memset(head,-1,sizeof(head));
tot=0;
}
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
}
void dfs(int cur,int f){
for(int i=1;i<=20;i++)
fa[cur][i]=fa[fa[cur][i-1]][i-1];
for(int i=head[cur];~i;i=e[i].next){
int to=e[i].to;
if(to==f)continue;
dis[to]=dis[cur]+1;
d[to]=d[cur]+1;
fa[to][0]=cur;
dfs(to,cur);
}
}
int lca(int a,int b){
if(d[a]<d[b])swap(a,b);
int x=d[a]-d[b],y=0;
while(x){
if(x&1)a=fa[a][y];
x>>=1;
++y;
}
if(a==b)return a;
for(int i=19;i>=0;i--){
if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
}
return fa[a][0];
}
int chu[MAXN];
int main()
{
int n;
while(~scanf("%d",&n)){
init();
memset(chu,0,sizeof(chu));
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
AddEdge(x,y);
++chu[x];
}
fa[1][0]=1;
dis[1]=0;
d[1]=0;
dfs(1,-1);
int maxn=0,maxu=1;
for(int i=1;i<=n;i++){
if(chu[i]==0&&dis[i]>maxn){
maxn=dis[i];
maxu=i;
}
}
int ans=maxn;
for(int i=1;i<=n;i++){
if(chu[i]==0&&maxu!=i){
int v=lca(maxu,i);
ans=max(ans,maxn+dis[i]-dis[v]);
}
}
printf("%d\n",ans);
}
return 0;
}
|
