C++-এ ট্রি-এ তিনটি নোড যাতে সংযোগ পথে নোড সংখ্যা ম্যাক্সিমাম হয়

সমস্যা

একটি ট্রি দেওয়া (N নোড)। তিনটি নোড বেছে নিন যাতে তাদের যেকোনো দুটির মধ্যে পথে পড়া নোডগুলোর ইউনিয়ন (union) এর আকার সর্বোচ্চ হয়।

অ্যালগরিদম: ট্রি ডায়ামিটার + থার্ড নোড

1. ট্রির ডায়ামিটার (সর্বোচ্চ দূরত্বের দুটি নোড u, v) বের করুন (দুইবার BFS/DFS)।
2. ডায়ামিটার পথের সব নোড চিহ্নিত করুন।
3. ডায়ামিটার পথের প্রতিটি নোড থেকে সাবট্রি-তে গিয়ে সবচেয়ে গভীর লিফ w খুঁজুন।
4. ত্রয়োদশ (u, v, w) হবে অপ্টিমাল।

C++ কোড (স্কেলেটন)

#include <bits/stdc++.h> 
#define ll long long
#define MAX 100005
using namespace std;

vector<int> adj[MAX];
bool vis[MAX], onDia[MAX];
int parent[MAX], N;
int startNode, endNode, midNode, maxDepth;

// DFS for diameter endpoints
void dfs1(int u, int d) { ... }
void dfs2(int u, int d) { ... } // with parent tracking
void dfs3(int u, int d) { ... } // off-diameter max depth

void solveTree() {
    dfs1(1,0); // find startNode
    fill(vis, vis+N+1, false);
    dfs2(startNode,0); // find endNode, parent[]
    // mark diameter path
    for (int x=endNode; x!=startNode; x=parent[x]) onDia[x]=true;
    onDia[startNode]=true;
    // find farthest off-diameter node
    maxDepth=-1;
    for (int i=1; i<=N; i++) if (onDia[i]) dfs3(i,0);
    cout << "Nodes: (" << startNode << ", " << endNode << ", " << midNode << ")";
}

নমুনা আউটপুট

Nodes: (0, 0, 0)

নোট: নমুনা ইনপুট/আউটপুট এডহক। মূল লজিক ডায়ামিটার + থার্ড নোড।