Need Help in "Three Paths on a Tree "

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";
}


@galencolin @everule1

An easy way to prove it is to draw the diameter as a horizontal line and then there are trees connected to each node of the diameter. Then it is easy to visualise and prove.

3 Likes

As the editorial says -

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.

If anyone wants solution ( commented code ) , using diameter of tree + Multisource BFS

Check Here

1 Like