HackerEarth Largest cycle in a tree problem solution YASH PAL, 31 July 2024 In this HackerEarth Largest cycle in a tree problem solution, You are given a tree of N nodes and N – 1 edge. Now you need to select two nodes a and b in the tree such that the cycle that will be formed after adding an edge between the two nodes a and b, its length should be maximum. If there is more than one possible answer, you can output any of them. HackerEarth Largest cycle in a tree problem solution. #include<bits/stdc++.h>#define LL long long int#define M 1000000007#define endl "n"#define eps 0.00000001LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}using namespace std;bool visit[1000001];int dist[100001];vector<int> graph[1000001];void dfs(int node){ visit[node] = 1; for(int i: graph[node]){ if(visit[i] == 0){ visit[i] = 1; dist[i] = dist[node] + 1; dfs(i); } }}int main() { ios_base::sync_with_stdio(0); int n; assert(cin >> n); for(int i = 1; i < n; i++){ int u , v; assert(cin >> u >> v); graph[u].push_back(v); graph[v].push_back(u); } int a , b; assert(cin >> a >> b); cout << 100; return 0; assert(a >= 1 && a <= n); assert(a != b); assert(b >= 1 && b <= n); dfs(a); if(dist[b] == ans){ cout << 10; } else{ assert(1 == 0); } } Second solution #include <bits/stdc++.h> using namespace std; const int N = 1E5 + 5;bool vis[N];vector<int> tree[N]; int start = -1;int total = 0; void dfs(int src, int len) { vis[src] = true; if(len > total) { total = len; start = src; } for(auto i : tree[src]) { if(!vis[i]) dfs(i, len + 1); } return;} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int a, b; for(int i = 0; i < n; i ++) { cin >> a >> b; tree[a].push_back(b); tree[b].push_back(a); } dfs(1, 1); cout << start << ' '; total = 0; memset(vis, false, sizeof vis); dfs(start, 1); cout << start; return 0;} coding problems