Hi, I was solving Three Paths on a Tree, intuitively it seems that including the 2 ends of the diameter of the tree is an optimal choice for the solution and it turns out that my solution passed too with the above logic but I am not able to prove that it’s always optimal to include the diameter in the solution can somebody please help me with proving it?
AC_SOLUTION_FOR REFERENCE
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=1;i<=n;i++)
#define pb push_back
using namespace std;
const long mxN =2e5+2 ;
int n,anc[mxN][18],d[mxN];
vector<int>adj[mxN] ;
void dfs(int v,int p){
anc[v][0]=p ;if(~p)d[v]=d[p]+1 ;
for(int i=1;i<18;i++)
anc[v][i]=~anc[v][i-1]?anc[anc[v][i-1]][i-1]:-1 ;
for(int x:adj[v])
if(x^p)
dfs(x,v) ;
}
int lca(int u,int v){
if(d[u]<d[v])
swap(u,v) ;
for(int i=17;~i;--i)
if(d[u]-(1<<i)>=d[v])
u=anc[u][i] ;
if(u==v)
return u ;
for(int i =17;~i;--i){
if(anc[u][i]^anc[v][i]){
u=anc[u][i],v=anc[v][i] ;
}
}
return anc[u][0] ;
}
void dfs1(int v,int p=-1){
if(~p)d[v]=d[p]+1 ;
for(int x:adj[v])
if(x^p)
dfs1(x,v);
}
int main() {
cin >> n;
FOR(i,n-1){
int a,b;cin >> a >>b;
adj[a].pb(b);adj[b].pb(a);
}
int a,b,c,ds=-1;
dfs1(1) ;
FOR(i,n)
if(d[i]>ds)
ds=d[i],a=i ;
memset(d,0,sizeof(d));dfs1(a) ;ds=-1 ;
FOR(i,n)
if(d[i]>ds)
ds=d[i],b=i ;
int ans =ds ;
memset(d,0,sizeof(d));dfs(a,-1) ;ds=-1 ;
FOR(i,n)
if(d[i]-d[lca(b,i)]>ds&&i^a&&i^b)
ds=d[i]-d[lca(b,i)],c=i ;
cout << ans +ds << "\n";
cout << a << " "<< b << " "<< c << "\n";
}