专栏首页glm的全栈学习之路Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

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

F. Three Paths on a Tree

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.

题意:找出树上三个点,满足这三个点相互形成的简单路径的边并集最大

直觉告诉我们:有两个点一定是直径的两个端点,嗯,你没错,这两个点怎么求?随便找一个点bfs出来一个端点,然后再以这个端点bfs一次出来另一个端点,ok

剩下一个点如何确定?到两个点距离和最大即可,在两次bfs过程中保留两个端点到任意点的距离然后找这个最大值就好

#include<bits/stdc++.h>
#define ll long long
#define rg register ll
using namespace std;
ll n;
ll head[200005],cnt,dis[200005],vis[200005],maxdis,dis1[200005],dis2[200005];
struct node
{
    ll to,next,val;
}edge[400005];
inline void add(ll u,ll v,ll val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
inline ll bfs(ll x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    queue<ll>q;
    q.push(x);
    vis[x]=1;
    ll now;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(rg i=head[now];~i;i=edge[i].next)
        {
            ll to=edge[i].to;
            if(!vis[to])
            {
                q.push(to);
                vis[to]=1;
                dis[to]=dis[now]+edge[i].val;
                maxdis=max(maxdis,dis[to]);
            }
        }
    }
    return now;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n;
    for(rg i=1;i<n;i++)
    {
        ll a,b;
        cin>>a>>b;
        add(a,b,1),add(b,a,1);
    }
    ll ans1=bfs(1);
    ll ans2=bfs(ans1);
    for(rg i=1;i<=n;i++)dis1[i]=dis[i];
    bfs(ans2);
    for(rg i=1;i<=n;i++)dis2[i]=dis[i];
    ll ans3=0,ans=0;
    for(rg i=1;i<=n;i++)
    {
        if((dis1[i]+dis2[i]+maxdis)/2>ans&&i!=ans1&&i!=ans2)ans=(dis1[i]+dis2[i]+maxdis)/2,ans3=i;
    }
    cout<<ans<<endl<<ans1<<" "<<ans2<<" "<<ans3<<endl;
    while(1)getchar();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Educational Codeforces Round 81 (Rated for Div. 2) A. Display The Number

    You have a large electronic screen which can display up to 998244353998244353 de...

    glm233
  • Codeforces Beta Round #14 (Div. 2)A. Letter

    A boy Bob likes to draw. Not long ago he bought a rectangular graph (checked) sh...

    glm233
  • 2018-2019 ICPC, NEERC, Southern Subregional Contest D. Garbage Disposal

    Enough is enough. Too many times it happened that Vasya forgot to dispose of gar...

    glm233
  • 移动购物应用的兴起

    在大流行中,移动购物应用程序已成为在线零售业务的中心,显然,它们将继续存在。实际上,到2021年,移动电子商务或移动商务的销售额预计将占所有零售电子商务销售额的...

    YH
  • WEE &SEE角色设定

    腾讯ISUX
  • Know Kubernetes — Pictorially

    Recently, I started my Kubernetes journey and wanted to understand its internals...

    麒思妙想
  • Qualcomm - SnapDragon Tech Summit - Key Note - About 5G

    Qualcomm SnapDragon Tech Summit首日Keynote。 Qualcomm对5G现状和未来的理解,及其技术框架。非常重要。

    用户6026865
  • 开源工作报告显示更多的空缺,更少的人(IT)

    Linux基金会和学习平台edX周一发布了最新的开源就业报告,自两年前的上一份报告以来,该报告更新了技术招聘情况。研究表明,尽管发生了大流行,但对开源技术技能的...

    用户8054058
  • Mutex VS. Semaphore

    The key point is that mutexes should be used to protect shared resources, while ...

    lesM10
  • [Hot Technology系列]从此之后再无Load Balancer--SmartStack

    什么是SmartStack? SmartStack is an automated service discovery and registration fr...

    包子面试培训

扫码关注云+社区

领取腾讯云代金券