So in this problem [problem:1294F]. The editorial solution is this :↵
↵
<spoiler summary="Spoiler">↵
↵
Firstly, let's find some diameter of the tree. Let a and b be the endpoints of this diameter (and first two vertices of the answer). You can prove yourself why it is always good to take the diameter and why any diameter can be taken in the answer. Then there are two cases: the length of the diameter is n−1 or the length of the diameter is less than n−1. In the first case, you can take any other vertex as the third vertex of the answer c, it will not affect the answer anyway. Otherwise, we can run multi-source bfs from all vertices of the diameter and take the farthest vertex as the third vertex of the answer. It is always true because we can take any diameter and the farthest vertex will increase the answer as much as possible.↵
↵
↵
</spoiler>↵
↵
Suppose our tree has 23 nodes. Let the diameter contains all the node b/w 1 and 20 (take in increasing order for simplicity).↵
Lets take a branch from node 5 which contains the remaining nodes . So according to the editorial we use multi-source bfs and find the node which is at farthest distance . The node that will be farthest will be around node 9 or 10. But if we take this as third node the result will be (1 , 20 , (9 or 10)) but this will not increase the result we will still get 19 edges as our answer. Rather we should take a branch with is at max distance from any node on diameter. I tried this approach but it is giving MLE . Here is the code:↵
↵
<spoiler summary="Spoiler">↵
#pragma GCC optimize("Ofast")↵
#pragma GCC target("avx,avx2,fma")↵
#include <bits/stdc++.h>↵
#include<ext/pb_ds/assoc_container.hpp>↵
#include<ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace chrono;↵
using namespace __gnu_pbds;↵
↵
↵
#define int long long↵
#define all(a) a.begin(),a.end()↵
#define endl "\n"↵
#define pb push_back↵
#define pii pair<int , int>↵
#define ff first↵
#define ss second↵
#define input(a) for(auto &it : a)cin >> it;↵
#define output(a) for(auto it : a)cout << it << " ";↵
#define FOR_IN(a, b , v) for(int i = a ; i < b ; i++) cin >> v[i];↵
#define FOR_OUT(a, b , v) for(int i = a ; i < b ; i++) cout << v[i] << " ";↵
#define fill(a,b) memset(a, b, sizeof(a))↵
↵
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}↵
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}↵
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;}↵
int ceil(int n , int k) {return ((n + k — 1) / k);}↵
↵
↵
const int maxN = 1e5 + 10;↵
const int maxN2 = 2 * 1e5 + 10;↵
const int maxN3 = 1e6 + 10;↵
const int INF = 1e18;↵
int mod = 1e9 + 7;↵
↵
#ifndef ONLINE_JUDGE↵
#define debug(x) \↵
cerr << (#x) << " is ";\↵
_print(x)↵
#define dbg(x) \↵
cerr << (#x) << " is " << x << endl;↵
#else↵
#define debug(x)↵
#define dbg(x)↵
#endif↵
↵
using ull = unsigned long long;↵
using lld = long double;↵
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key↵
↵
↵
void _print(int t) {cerr << t;}↵
void _print(string t) {cerr << t;}↵
void _print(char t) {cerr << t;}↵
void _print(lld t) {cerr << t;}↵
void _print(double t) {cerr << t;}↵
void _print(ull t) {cerr << t;}↵
↵
↵
template <class T, class V> void _print(pair <T, V> p);↵
template <class T> void _print(vector <T> v);↵
template <class T> void _print(set <T> v);↵
template <class T, class V> void _print(map <T, V> v);↵
template <class T> void _print(multiset <T> v);↵
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; cerr << endl;}↵
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
↵
// Memory Exceed || Time Exceed --> Reason Canbe long long↵
vector<int>adj[maxN2];↵
vector<int>depth , dist;↵
vector<int>path , level;↵
vector<int>new_depth;↵
void dfs1(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dist[v] = min(dist[v] , dist[u] + 1);↵
dfs1(v , u);↵
}↵
}↵
void dfs2(int u , int p , int target , vector<int> ans)↵
{↵
ans.push_back(u);↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dfs2(v, u, target , ans);↵
}↵
if (u == target)↵
{↵
path = ans;↵
}↵
ans.pop_back();↵
}↵
void dfs3(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p) continue;↵
dfs3(v , u);↵
depth[u] = max(depth[u] , 1 + depth[v]);↵
}↵
}↵
void dfs4(int u , int p , int lvl , int & w)↵
{↵
if (lvl == 0)↵
{↵
w = u;↵
return;↵
}↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dfs4(v , u , lvl — 1 , w);↵
}↵
}↵
↵
void new_dfs(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
new_depth[v] = new_depth[u] + 1;↵
new_dfs(v , u);↵
}↵
}↵
void solve()↵
{↵
int n ; cin >> n;↵
for (int i = 0 ; i < n — 1 ; i++)↵
{↵
int u , v ; cin >> u >> v;↵
u--; v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
depth.assign(n, 0); dist.assign(n, INF);↵
dist[0] = 0;↵
dfs1(0 , -1);↵
int u = max_element(all(dist)) — dist.begin();↵
dist.assign(n, INF);↵
dist[u] = 0;↵
dfs1(u , -1);↵
int v = max_element(all(dist)) — dist.begin();↵
dfs2(v , -1 , u , {});↵
int ans = path.size() — 1;↵
int w = -1;↵
depth.assign(n , 0);↵
dfs3(v , 0);↵
set<int>st(all(path));↵
new_depth.assign(n , 0);↵
for (int i = 1 ; i < path.size() — 1 ; i++)↵
{↵
int node = path[i];↵
for (auto v : adj[node])↵
{↵
if (st.find(v) != st.end())continue;↵
new_depth[v] = 1;↵
new_dfs(v , node);↵
}↵
}↵
if (path.size() == n)↵
{↵
for (auto p : path)↵
{↵
if (p == u || p == v)continue;↵
w = p;↵
break;↵
}↵
cout << ans << endl;↵
cout << u + 1 << " " << v + 1 << " " << w + 1 << endl;↵
return;↵
}↵
// debug(new_depth);↵
cout << ans + *max_element(all(new_depth)) << endl;↵
cout << u + 1 << " " << v + 1 << " " << (max_element(all(new_depth)) — new_depth.begin()) + 1 << endl;↵
}↵
↵
signed main () {↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt" , "r", stdin);↵
freopen("output.txt" , "w", stdout);↵
freopen("error.txt" , "w" , stderr);↵
#endif↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
int t = 1;↵
// cin >> t;↵
while (t--)solve();↵
}↵
</spoiler>↵
↵
[submission:238471077]
↵
<spoiler summary="Spoiler">↵
↵
Firstly, let's find some diameter of the tree. Let a and b be the endpoints of this diameter (and first two vertices of the answer). You can prove yourself why it is always good to take the diameter and why any diameter can be taken in the answer. Then there are two cases: the length of the diameter is n−1 or the length of the diameter is less than n−1. In the first case, you can take any other vertex as the third vertex of the answer c, it will not affect the answer anyway. Otherwise, we can run multi-source bfs from all vertices of the diameter and take the farthest vertex as the third vertex of the answer. It is always true because we can take any diameter and the farthest vertex will increase the answer as much as possible.↵
↵
↵
</spoiler>↵
↵
Suppose our tree has 23 nodes. Let the diameter contains all the node b/w 1 and 20 (take in increasing order for simplicity).↵
Lets take a branch from node 5 which contains the remaining nodes . So according to the editorial we use multi-source bfs and find the node which is at farthest distance . The node that will be farthest will be around node 9 or 10. But if we take this as third node the result will be (1 , 20 , (9 or 10)) but this will not increase the result we will still get 19 edges as our answer. Rather we should take a branch with is at max distance from any node on diameter. I tried this approach but it is giving MLE . Here is the code:↵
↵
#pragma GCC optimize("Ofast")↵
#pragma GCC target("avx,avx2,fma")↵
#include <bits/stdc++.h>↵
#include<ext/pb_ds/assoc_container.hpp>↵
#include<ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace chrono;↵
using namespace __gnu_pbds;↵
↵
↵
#define int long long↵
#define all(a) a.begin(),a.end()↵
#define endl "\n"↵
#define pb push_back↵
#define pii pair<int , int>↵
#define ff first↵
#define ss second↵
#define input(a) for(auto &it : a)cin >> it;↵
#define output(a) for(auto it : a)cout << it << " ";↵
#define FOR_IN(a, b , v) for(int i = a ; i < b ; i++) cin >> v[i];↵
#define FOR_OUT(a, b , v) for(int i = a ; i < b ; i++) cout << v[i] << " ";↵
#define fill(a,b) memset(a, b, sizeof(a))↵
↵
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}↵
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}↵
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;}↵
int ceil(int n , int k) {return ((n + k — 1) / k);}↵
↵
↵
const int maxN = 1e5 + 10;↵
const int maxN2 = 2 * 1e5 + 10;↵
const int maxN3 = 1e6 + 10;↵
const int INF = 1e18;↵
int mod = 1e9 + 7;↵
↵
#ifndef ONLINE_JUDGE↵
#define debug(x) \↵
cerr << (#x) << " is ";\↵
_print(x)↵
#define dbg(x) \↵
cerr << (#x) << " is " << x << endl;↵
#else↵
#define debug(x)↵
#define dbg(x)↵
#endif↵
↵
using ull = unsigned long long;↵
using lld = long double;↵
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key↵
↵
↵
void _print(int t) {cerr << t;}↵
void _print(string t) {cerr << t;}↵
void _print(char t) {cerr << t;}↵
void _print(lld t) {cerr << t;}↵
void _print(double t) {cerr << t;}↵
void _print(ull t) {cerr << t;}↵
↵
↵
template <class T, class V> void _print(pair <T, V> p);↵
template <class T> void _print(vector <T> v);↵
template <class T> void _print(set <T> v);↵
template <class T, class V> void _print(map <T, V> v);↵
template <class T> void _print(multiset <T> v);↵
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; cerr << endl;}↵
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]"; cerr << endl;}↵
↵
// Memory Exceed || Time Exceed --> Reason Canbe long long↵
vector<int>adj[maxN2];↵
vector<int>depth , dist;↵
vector<int>path , level;↵
vector<int>new_depth;↵
void dfs1(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dist[v] = min(dist[v] , dist[u] + 1);↵
dfs1(v , u);↵
}↵
}↵
void dfs2(int u , int p , int target , vector<int> ans)↵
{↵
ans.push_back(u);↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dfs2(v, u, target , ans);↵
}↵
if (u == target)↵
{↵
path = ans;↵
}↵
ans.pop_back();↵
}↵
void dfs3(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p) continue;↵
dfs3(v , u);↵
depth[u] = max(depth[u] , 1 + depth[v]);↵
}↵
}↵
void dfs4(int u , int p , int lvl , int & w)↵
{↵
if (lvl == 0)↵
{↵
w = u;↵
return;↵
}↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
dfs4(v , u , lvl — 1 , w);↵
}↵
}↵
↵
void new_dfs(int u , int p)↵
{↵
for (auto v : adj[u])↵
{↵
if (v == p)continue;↵
new_depth[v] = new_depth[u] + 1;↵
new_dfs(v , u);↵
}↵
}↵
void solve()↵
{↵
int n ; cin >> n;↵
for (int i = 0 ; i < n — 1 ; i++)↵
{↵
int u , v ; cin >> u >> v;↵
u--; v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
depth.assign(n, 0); dist.assign(n, INF);↵
dist[0] = 0;↵
dfs1(0 , -1);↵
int u = max_element(all(dist)) — dist.begin();↵
dist.assign(n, INF);↵
dist[u] = 0;↵
dfs1(u , -1);↵
int v = max_element(all(dist)) — dist.begin();↵
dfs2(v , -1 , u , {});↵
int ans = path.size() — 1;↵
int w = -1;↵
depth.assign(n , 0);↵
dfs3(v , 0);↵
set<int>st(all(path));↵
new_depth.assign(n , 0);↵
for (int i = 1 ; i < path.size() — 1 ; i++)↵
{↵
int node = path[i];↵
for (auto v : adj[node])↵
{↵
if (st.find(v) != st.end())continue;↵
new_depth[v] = 1;↵
new_dfs(v , node);↵
}↵
}↵
if (path.size() == n)↵
{↵
for (auto p : path)↵
{↵
if (p == u || p == v)continue;↵
w = p;↵
break;↵
}↵
cout << ans << endl;↵
cout << u + 1 << " " << v + 1 << " " << w + 1 << endl;↵
return;↵
}↵
// debug(new_depth);↵
cout << ans + *max_element(all(new_depth)) << endl;↵
cout << u + 1 << " " << v + 1 << " " << (max_element(all(new_depth)) — new_depth.begin()) + 1 << endl;↵
}↵
↵
signed main () {↵
#ifndef ONLINE_JUDGE↵
freopen("input.txt" , "r", stdin);↵
freopen("output.txt" , "w", stdout);↵
freopen("error.txt" , "w" , stderr);↵
#endif↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
int t = 1;↵
// cin >> t;↵
while (t--)solve();↵
}↵
</spoiler>↵
↵
