codeforce 1294F-Three Paths on a Tree【树的直径+多源bfs】

  一开始认为根节点和深度最深的节点一定要选择（其实是错的），确定了两个点后枚举第三个点，用倍增求深度最深的点和枚举的点的lca,确定第三个点。

正解：

  用两次 $dfs$dfs 求出树的直径的两个端点，即可求得两个点。如果直径长度 $=n-1$=n−1，那么第三个点可以任意选择。如果不是，用多源 $bfs$bfs 求出离直径最远的点即为第三个点。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef pair<int,int> P;
vector<int>pic[N];
int pre[N],m,maxn;
bool vis[N];
queue<P>que;
int a,b,c,n;
void dfs(int v,int p,int d)
{
    pre[v]=p;
    if(d>maxn)
    {
        maxn=d;
        m=v;
    }
    for(int i=0;i<pic[v].size();i++)
    {
        if(pic[v][i]!=p)
            dfs(pic[v][i],v,d+1);
    }
}
void bfs()
{
    memset(vis,0,sizeof(vis));
    while(!que.empty())
        que.empty();
    int p=b;
    while(p!=-1)
    {
        vis[p]=1;
        que.push(make_pair(0,p));
        p=pre[p];
    }
    while(!que.empty())
    {
        P now=que.front();
        que.pop();
        if(now.first>maxn)
        {
            maxn=now.first;
            c=now.second;
        }
        for(int i=0;i<pic[now.second].size();i++)
        {
            int t=pic[now.second][i];
            if(!vis[t])
            {
                que.push(make_pair(now.first+1,t));
                vis[t]=1;
            }
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int u,v,ans=0;
        for(int i=1;i<=n;i++)
            pic[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            pic[u].push_back(v);
            pic[v].push_back(u);
        }
        maxn=0;
        dfs(1,-1,0);
        a=m;
        maxn=0;
        dfs(a,-1,0);
        b=m;
        ans=maxn;
        if(ans==n-1)
        {
            for(int i=1;i<=3;i++)
            {
                if(i!=a&&i!=b)
                {
                    c=i;
                    break;
                }
            }
            printf("%d\n%d %d %d\n",n-1,a,b,c);
        }
        else
        {
            maxn=0;
            bfs();
            ans+=maxn;
            printf("%d\n%d %d %d\n",ans,a,b,c);
        }
    }
    return 0;
}