หา Triplet ของโหนดใน Tree ที่ครอบคลุม Nodes มากที่สุดใน Path ระหว่างกันใน C++

โจทย์: Tree N nodes หา triplet (a,b,c) ที่ nodes ใน paths ระหว่างคู่ๆ (a-b, b-c, a-c) รวมกันมากที่สุด

แนวคิด: Diameter + Farthest from Diameter

1. หา diameter endpoints (u, v) ด้วย 2 BFS/DFS
2. Mark ทุกโหนดบน diameter path 3. หาโหนด w ที่ห่างจาก diameter มากที่สุด (max distance to any node on diameter) 4. Triplet = (u, v, w)

ตัวอย่างโค้ด C++ (โครงสร้างหลัก)

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

vector<int> adj[MAX];
bool visited[MAX];
int parent[MAX], maxDist = -1;
int startNode, endNode, midNode;

void dfs1(int u, int dist) { // หา endNode จาก startNode
    visited[u] = true;
    bool leaf = true;
    for (int v : adj[u]) if (!visited[v]) {
        leaf = false; parent[v] = u; dfs1(v, dist+1);
    }
    if (leaf && maxDist < dist) { maxDist = dist; endNode = u; }
}

void dfs2(int u, int dist) { // หา midNode ไกลที่สุดจาก diameter
    visited[u] = true;
    bool leaf = true;
    for (int v : adj[u]) if (!visited[v] && !onDiameter[v]) {
        leaf = false; dfs2(v, dist+1);
    }
    if (leaf && maxDist < dist) { maxDist = dist; midNode = u; }
}

int main() {
    // Build tree, run dfs1 from 1 → startNode
    // Reset, run dfs1 from startNode → endNode, record parent
    // Mark diameter path using parent
    // Reset, run dfs2 from all diameter nodes → midNode
    cout << "Nodes: (" << startNode << ", " << endNode << ", " << midNode << ")";
}

Complexity

• Time: O(N)
• Space: O(N)

หมายเหตุ: โค้ดต้นฉบับมี bug (graph construction ผิด) ตัวอย่างนี้เป็น logic ที่ถูกต้อง