萌新的思路是dfs记录一下每个结点向上走,向下走的最远与次远距离,然后枚举每个结点统计答案,然而在 #2 就 WA 了qwq
# include <bits/stdc++.h>
# define pii pair<int,int>
using namespace std;
const int N = 2e5 + 7;
int n;
struct edge {
int nxt, v;
}e[N<<1];
struct qwq {
int dis, pos;
}q;
int h[N], cnt;
inline void add_edge(int u, int v) {
e[++cnt].nxt = h[u], e[cnt].v = v;
h[u] = cnt;
}
pii dep[N][2], up[N];
inline bool cmp(pii a, pii b) {
return a.first < b.first;
}
inline void dfs(int u, int fa) {
dep[u][0].first = 1; dep[u][0].second = u;
dep[u][1].first = -1e8;
for ( int i = h[u]; i; i = e[i].nxt ) {
int v = e[i].v ; if ( v == fa ) continue;
dfs(v, u); pii qwqwq = dep[v][0]; qwqwq.first++;
pii p[3] = {dep[u][1], dep[u][0], qwqwq};
sort(p, p + 3, cmp);
dep[u][0] = p[2], dep[u][1] = p[1];
}
}
inline void dfs2(int u, int fa) {
for ( int i = h[u]; i; i = e[i].nxt ) {
int v = e[i].v; if ( v == fa ) continue;
pii tmp = dep[u][0].first == dep[v][0].first + 1 ? dep[u][1] : dep[u][0];
tmp.first -- ;
if (up[u].first > tmp.first) up[v] = up[u], up[v].first ++;
else up[v] = tmp, up[v].first ++;
dfs2(v, u);
}
}
int main () {
ios :: sync_with_stdio(false);
cin . tie(0), cout . tie(0);
cin >> n;
for ( int i = 1; i < n ; i ++ ) {
int u, v; cin >> u >> v;
add_edge(u, v), add_edge(v, u);
}
dfs(1, 0); dfs2(1, 0); int ans = 0; int pos;
// for ( int i = 1; i <= n ; i ++ )
// cout << dep[i][0] << " " << dep[i][1] << " " << up[i] << "\n";
for ( int i = 1; i <= n ; i ++ ) {
if ( dep[i][0].first + dep[i][1].first + up[i].first - 2 > ans)
ans = dep[i][0].first + dep[i][1].first + up[i].first - 2,
pos = i;
}
cout << ans << "\n";
cout << dep[pos][0].second << " " << dep[pos][1].second << " " << up[pos].second << "\n";
return 0;
}