Maximize Longest path - hackerRank Stryker world code sprint - study code - https://www.hackerrank.com/_mfv_

MaximizeLongestpath_studyCode1.cpp

#pragma GCC diagnostic ignored "-Wunused-result"

#include <cstdio>
#include <cstdlib>
#include <vector>

struct Node {

	std::vector<int> children;

	int parent;
	
	int maxInSubtree;

	int maxInChild;

	int maxInChild2;
	
	int maxFromChild;

	int maxFromChild2;

	int maxFromChild3;
};

void fillDown(int x, int parent, std::vector<Node> &nodes) {
	Node &node = nodes[x];
	node.maxInSubtree = 0;
	node.maxInChild = 0;
	node.maxInChild2 = 0;
	node.maxFromChild = 0;
	node.maxFromChild2 = 0;
	node.maxFromChild3 = 0;
	for (int c : node.children) {
		if (c == parent) {
			continue;
		}
		fillDown(c, x, nodes);
		{
			int t = nodes[c].maxInSubtree;
			if (t > node.maxInChild) {
				node.maxInChild2 = node.maxInChild;
				node.maxInChild = t;
			} else if (t > node.maxInChild2) {
				node.maxInChild2 = t;
			}
		}
		{
			int t = nodes[c].maxFromChild + 1;
			if (t > node.maxFromChild) {
				node.maxFromChild3 = node.maxFromChild2;
				node.maxFromChild2 = node.maxFromChild;
				node.maxFromChild = t;
			} else if (t > node.maxFromChild2) {
				node.maxFromChild3 = node.maxFromChild2;
				node.maxFromChild2 = t;
			} else if (t > node.maxFromChild3) {
				node.maxFromChild3 = t;
			}
		}
	}
	node.maxInSubtree = std::max(node.maxInChild, node.maxFromChild + node.maxFromChild2);
}

void findMax(int x, int parent, int maxInTop, int maxFromTop, std::vector<Node> &nodes, int &max) {
	if (parent == -1) {
		max = std::max(max, nodes[x].maxInSubtree);
	} else {
		max = std::max(max, nodes[x].maxInSubtree + 1 + maxInTop);
	}
	for (int c : nodes[x].children) {
		if (c == parent) {
			continue;
		}
		int mft = maxFromTop;
		int mit = maxInTop;
		if (nodes[c].maxFromChild + 1 == nodes[x].maxFromChild) {
			mft = std::max(mft, nodes[x].maxFromChild2);
			mit = std::max(mit, std::max(maxFromTop, nodes[x].maxFromChild3) + nodes[x].maxFromChild2);
		} else if (nodes[c].maxFromChild + 1 == nodes[x].maxFromChild2) {
			mft = std::max(mft, nodes[x].maxFromChild);
			mit = std::max(mit, std::max(maxFromTop, nodes[x].maxFromChild3) + nodes[x].maxFromChild);
		} else {
			mft = std::max(mft, nodes[x].maxFromChild);
			mit = std::max(mit, std::max(maxFromTop, nodes[x].maxFromChild2) + nodes[x].maxFromChild);
		}
		if (nodes[c].maxInSubtree == nodes[x].maxInChild) {
			mit = std::max(mit, nodes[x].maxInChild2);
		} else {
			mit = std::max(mit, nodes[x].maxInChild);
		}
		mft++;
		findMax(c, x, mit, mft, nodes, max);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	std::vector<Node> nodes(n);
	for (int i = 1; i < n; i++) {
		int v1, v2;
		scanf("%d %d", &v1, &v2);
		v1--;
		v2--;
		nodes[v1].children.push_back(v2);
		nodes[v2].children.push_back(v1);
	}
	const int start = 0;
	fillDown(start, -1, nodes);
	int max = 0;
	findMax(start, -1, 0, 0, nodes, max);
	printf("%d", max);
	return 0;
}