题目描述
You are given an unweighted tree with n vertices. Recall that a tree is a connected undirected graph without cycles.
Your task is to choose three distinct vertices a,b,c on this tree such that the number of edges which belong to at least one of the simple paths between a and b, b and c, or a and c 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.
输入描述
The first line contains one integer number n $(3≤n≤2⋅10^5)$ — the number of vertices in the tree.
Next n−1 lines describe the edges of the tree in form $a_i,b_i (1≤a_i, b_i≤n, a_i≠b_i)$. It is guaranteed that given graph is a tree.
输出描述
In the first line print one integer res — the maximum number of edges which belong to at least one of the simple paths between a and b, b and c, or a and c.
In the second line print three integers a,b,c such that 1≤a,b,c≤n and a≠,b≠c,a≠c.
If there are several answers, you can print any.
思路分析
一个树，找到三个点，使这三个点之间的路径的边数之和最大，相同边不重复计算。
- 可以确定其中两个点一定是树的直径的两个端点。
- 最后一个端点为直径上一个点，往非直径方向扩展的最深的点。
两次dfs确定直径端点，并标记直径。
第三次dfs确定深度最深的第三个点。
样例输入
8
1 2
2 3
3 4
4 5
4 6
3 7
3 8
样例输出
5
1 8 6
AC代码
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=2e5+10;
int n;
vector<int>e[N];
int dep[N],fa[N],vis[N];
void dfs(int u){
if(vis[u])
dep[u]=1;
else
dep[u]=dep[fa[u]]+1;
for(auto v:e[u]){
if(v==fa[u])
continue;
fa[v]=u;
dfs(v);
}
}
int main() {
IOS;
#ifdef xiaofan
freopen("in.txt","r",stdin);
#endif
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].pb(v);
e[v].pb(u);
}
int a=0,b=0,c=0,sum=0;
dfs(1);
for(int i=1;i<=n;i++)
if(dep[i]>dep[a])
a=i;
fa[a]=0;
dfs(a);
for(int i=1;i<=n;i++)
if(dep[i]>dep[b] && a!=i)
b=i;
int x=b;
while(x){
vis[x]=1;
x=fa[x];
sum++;
}
dfs(a);
for(int i=1;i<=n;i++)
if(dep[i]>dep[c]&& a!=i && b!=i)
c=i;
x=c;
while(!vis[x]){
vis[x]=1;
x=fa[x];
sum++;
}
cout<<sum-1<<endl;
cout<<a<<" "<<b<<" "<<c<<endl;
return 0;
}
