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


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