HackerEarth Largest Windmill problem solution

In this HackerEarth Largest Windmill problem solution We define a windmill graph as a graph G centered on node c with at least 5 adjacent paths. One of these paths has to have length at least 3 and it is interpreted as the base of the windmill. The remaining paths have length exactly 1 and are interpreted as the sails of the windmill.

For a given tree T with N nodes, the goal is to find the size of its largest subgraph (in terms of the number of nodes) which is a windmill graph and it’s center vertex. If there are many such largest subgraphs, take the one with the smallest center vertex. If no windmill graph is a subgraph of T, then the answer is 1.

HackerEarth Largest Windmill problem solution.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;

const int INF = 1e9;
const int N = 1e5;
const int REQ_ARMS = 5;
const int REQ_LONGEST_ARM = 3;

vi g[N];


bool visited[N];

int longest_down[N];
void dfs_longest_down(int v, int p) {
    assert(visited[v] == 0);
    visited[v] = 1;
    longest_down[v] = 0;
    for(int u : g[v]) {
        if (u == p) continue;
        dfs_longest_down(u, v);
        REMAX(longest_down[v], 1 + longest_down[u]);
    }
}

int res = -1;
int center_vertex = INF;
void dfs(int v, int p, int up) {
    int arms = 0;    
    int longest_arm = 0;
    int longest_arm_vertex = -1;
    int second_longest_arm = 0;
    if (up > 0) {
        arms = 1;
        longest_arm = up;
        longest_arm_vertex = p;
    }
    for(int u : g[v]) {
        if (u == p) continue;
        arms++;
        int tmp = 1 + longest_down[u];
        if (tmp > longest_arm) {
            second_longest_arm = longest_arm;
            longest_arm = tmp;
            longest_arm_vertex = u;
        } else if (tmp > second_longest_arm) {
            second_longest_arm = tmp;
        }
    }
    if (arms >= REQ_ARMS && longest_arm >= REQ_LONGEST_ARM) {
        int sz = 1 + arms - 1 + longest_arm;
        if (sz > res || (sz == res && v < center_vertex)) {
            res = sz;
            center_vertex = v;
        }
    }

    for(int u : g[v]) {
        if (u == p) continue;
        int new_up = (u != longest_arm_vertex) ? 1 + longest_arm : 1 + second_longest_arm;
        dfs(u, v, new_up);
    }
}

int main()    
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    assert(n >= 1 && n <= N);
    FOR(i, n-1) {
        int v, u;
        cin >> v >> u;
        assert(v >= 1 && v <= n);
        assert(u >= 1 && u <= n);
        assert(v != u);
        --v, --u;
        g[v].pb(u);
        g[u].pb(v);
    }
    dfs_longest_down(0, -1);
    FOR(i, n) assert(visited[i]);
    dfs(0, -1, 0);
    if (res == -1) {
        cout << -1 << endl;
    } else {
        cout << res << " " << center_vertex+1 << endl;
    }

    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int LGN = 18;
const int MAXN = 100005;
int farthest, par[MAXN][LGN], depth[MAXN];
vector <int> G[MAXN];
void dfs(int pos, int prev)
{
  depth[pos] = 1 + depth[prev];
  par[pos][0] = prev;
  if(depth[pos] > depth[farthest])
    farthest = pos;
  for (int i = 0; i < G[pos].size(); ++i)
  {
    if(G[pos][i] != prev)
      dfs(G[pos][i],pos);
  }
}
int lca(int u, int v)
{
  if(depth[u] < depth[v])
    return lca(v,u);
  int diff = depth[u] - depth[v];
  for (int i = 0; i < LGN; ++i)
  {
    if(diff & (1<<i))
      u = par[u][i];
  }
  if(u == v)
    return u;
  for (int i = LGN - 1; i >= 0; --i)
  {
    if(par[u][i] != par[v][i])
    {
      u = par[u][i];
      v = par[v][i];
    }
  }
  return par[u][0];
}
int get_dist(int u, int v)
{
  int l = lca(u,v);
  return (depth[u] + depth[v] - 2*depth[l]);
}
int main()
{
  int n;
  cin>>n;
  for (int i = 0; i < n - 1; ++i)
  {
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  farthest = 0;
  dfs(1,0);
  int dia1 = farthest;
  farthest = 0;
  dfs(dia1,0);
  int dia2 = farthest;
  for (int j = 1; j < LGN; ++j)
  {
    for (int i = 1; i <= n; ++i)
    {
      par[i][j] = par[par[i][j-1]][j-1];
    }
  }
  int ansval = -1, ans = -1;
  for (int i = 1; i <= n; ++i)
  {
    if(G[i].size() < 5)
      continue;
    int d = max(get_dist(i,dia1), get_dist(i,dia2));
    if(d < 3)
      continue;
    if(d + (int)G[i].size() > ansval)
    {
      ansval = d + (int)G[i].size();
      ans = i;
    }
  }
  if(ansval == -1)
    cout<<ansval<<"\n";
  else
    cout<<ansval<<" "<<ans<<"\n";
  return 0;
}