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.

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