Codeforces Round #615 (Div. 3) F. Three Paths on a Tree（树的直径，dfs）

Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

题目链接：https://codeforces.com/contest/1294/problem/F

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an unweighted tree with nn vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices a,b,ca,b,c on this tree such that the number of edges which belong to at least one of the simple paths between aa and bb, bb and cc, or aa and cc is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

Input

The first line contains one integer number nn (3≤n≤2⋅1053≤n≤2⋅105) — the number of vertices in the tree.

Next n−1n−1 lines describe the edges of the tree in form ai,biai,bi (1≤ai1≤ai, bi≤nbi≤n, ai≠biai≠bi). It is guaranteed that given graph is a tree.

Output

In the first line print one integer resres — the maximum number of edges which belong to at least one of the simple paths between aa and bb, bb and cc, or aa and cc.

In the second line print three integers a,b,ca,b,c such that 1≤a,b,c≤n1≤a,b,c≤n and a≠,b≠c,a≠ca≠,b≠c,a≠c.

If there are several answers, you can print any.

Example

input

Copy

8
1 2
2 3
3 4
4 5
4 6
3 7
3 8

output

Copy

5
1 8 6

Note

The picture corresponding to the first example (and another one correct answer):

If you choose vertices 1,5,61,5,6 then the path between 11 and 55 consists of edges (1,2),(2,3),(3,4),(4,5)(1,2),(2,3),(3,4),(4,5), the path between 11 and 66 consists of edges (1,2),(2,3),(3,4),(4,6)(1,2),(2,3),(3,4),(4,6) and the path between 55 and 66 consists of edges (4,5),(4,6)(4,5),(4,6). The union of these paths is (1,2),(2,3),(3,4),(4,5),(4,6)(1,2),(2,3),(3,4),(4,5),(4,6) so the answer is 55. It can be shown that there is no better answer.

题意：

给定一个含有n个节点的无根树，让你选出3个节点a,b,c， 使3个节点之间的最短路径中的边数最多。

思路：

可以证明：这3个点中一定有两个点是这棵树直径的断点，比如说是a,b。

那么我们需要先通过找树的直径确定ab后再寻找到使答案尽可能大的c节点。

我们来分类讨论：（很重要！

①：树的直径长度为n-1，那么树就是一个链，我们C点只要选择不是ab点的任意一个其他节点即可。

②：树的直径长度小于n-1，那么把a节点到b节点以及a和b简单路径中节点缩成一个节点n+1，然后重新建树，寻找与n+1距离最远的那个节点c即可。树缩点的方法是：dfs时用栈维护路径中的节点即可。

如果不会求树的直径，可以去搜个靠谱的博客看一下。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
// HFUU-QerM
// 16:42:43

int n;
std::vector<int> son1[maxn];
std::vector<int> son2[maxn];
int a, b, c;
int ans = 0;
int key = 0;
int m = -1;
void dfs1(int x, int pre, int cnt)
{
    if (cnt > m)
    {
        m = cnt;
        if (key == 0)
        {
            a = x;
        } else if (key == 1)
        {
            b = x;
        }
    }
    for (auto y : son1[x])
    {
        if (y != pre)
        {
            dfs1(y, x, cnt + 1);
        }
    }
}
stack<int> st;
int belong[maxn];
void dfs2(int x, int pre)
{
    st.push(x);
    if (x == b)
    {
        while (!st.empty())
        {
            belong[st.top()] = n + 1;
            st.pop();
        }
        key = 2;
        return ;
    }
    for (auto y : son1[x])
    {
        if (y != pre)
        {
            dfs2(y, x);
        }
        if (key == 2)
        {
            return ;
        }
    }
    st.pop();
}
void dfs3(int x, int pre, int cnt)
{
    if (cnt > m)
    {
        m = cnt;
        c = x;
    }
    for (auto y : son2[x])
    {
        if (y != pre)
        {
            dfs3(y, x, cnt + 1);
        }
    }
}
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    n = readint();
    repd(i, 1, n - 1)
    {
        int x, y;
        x = readint();
        y = readint();
        son1[x].push_back(y);
        son1[y].push_back(x);
    }
    m = -1;
    dfs1(1, 0, 0);
    key = 1;
    m = -1;
    dfs1(a, 0, 0);
    ans += m;
    repd(i, 1, n)
    {
        belong[i] = i;
    }
    dfs2(a, 0);
    repd(i, 1, n)
    {
        for (auto y : son1[i])
        {
            if (belong[y] != belong[i])
            {
                son2[belong[y]].push_back(belong[i]);
            }
        }
    }
    m = -1;
    dfs3(n + 1, 0, 0);
    ans += m;
    printf("%d\n", ans );
    if (c == n + 1)
    {
        repd(i, 1, n)
        {
            if (i == a || i == b)
            {
                continue;
            }
            c = i;
            break;
        }
    }
    printf("%d %d %d\n", a, b, c );
    return 0;
}