F. Three Paths on a Tree

题意

给一个树，让在树上找三个结点A，B，C，使得ABC三个结点3条路径中出现的结点数最多

分析

因为这是一棵树，三条路径必定会有一个交点O，所以我们需要让OA+OB+OC的长度尽可能的长，而OA+OB我们可以直接认为是树的直径，OC认为是这条直径上最长的一个分支。

具体做法

这里我用的是两次DFS求树的直径以及经过的路径结点，
第一次DFS：先从任意一个结点开始DFS到最远的距离，保存最远点A
第二次DFS：从A再进行一次DFS到最远的距离B，并且记录B->A的路径(倒着存的)
此时就以及求出了直径了，也就是OA+OB
第一次遍历直径中的结点，在vis[]数组上做访问标记
第二次遍历直接中的结点，对每一个结点进行DFS寻找最远的分支C点(访问过的不再访问)
最后答案ABC都求出来了

DFS遍历次数比较多，但是总共遍历树只会遍历3次 也就是O(3*n)

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;


int N,A,B,C,mx;
int h[maxn],e[maxn],ne[maxn],idx;
int last[maxn],vis[maxn];

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void DFS(int u,int fa = -1,int dis = 0){
    if(dis>=mx){
        A = u;
        mx = dis;
    }
    for(int i = h[u];i!=-1;i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        DFS(v,u,dis+1);
    }
}
void DFS2(int u,int fa = -1,int dis = 0){
    last[u] = fa;
    if(dis>=mx) {
        B = u,mx = dis;
    }
    for(int i = h[u];i!=-1;i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        DFS2(v,u,dis+1);
    }
}
void DFS3(int u,int fa = -1,int dis = 0){
    if(dis>=mx){
        C = u,mx = dis;
    }
    for(int i = h[u];i!=-1;i = ne[i]){
        int v = e[i];
        if(v == fa || vis[v]) continue;
        DFS3(v,u,dis+1);
    }
}
int main(){
    cin>>N;
    int a,b;
    memset(h,-1,sizeof(h));
    for(int i = 0;i<N-1;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    mx = 0;DFS(1);
    mx = 0;DFS2(A);

    vis[B] = 1;vis[A] = 1;
    for(int i = last[B];i!=A;i = last[i]) {
        vis[i] = 1;
    }
    int d = mx;mx = 0;
    for(int i = last[B];i!=A;i = last[i]) DFS3(i);
    cout<<d+mx<<endl;
    cout<<A<<" "<<B<<" "<<C<<endl;
    return 0;
}