// Tree diameter algorithm
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class TreeDiameter {
private:
    int n;
    vector<vector<pair<int, long long>>> adj;
    
    // BFS to find farthest node
    pair<int, long long> bfs(int start) {
        vector<long long> dist(n, -1);
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        
        int farthest = start;
        long long maxDist = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (auto [v, weight] : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + weight;
                    q.push(v);
                    
                    if (dist[v] > maxDist) {
                        maxDist = dist[v];
                        farthest = v;
                    }
                }
            }
        }
        
        return {farthest, maxDist};
    }
    
    // DFS to calculate diameter
    pair<long long, long long> dfs(int u, int parent) {
        long long max1 = 0, max2 = 0; // Longest and second longest paths
        
        for (auto [v, weight] : adj[u]) {
            if (v != parent) {
                auto [childMax, childDiameter] = dfs(v, u);
                diameter = max(diameter, childDiameter);
                
                long long pathLen = childMax + weight;
                if (pathLen > max1) {
                    max2 = max1;
                    max1 = pathLen;
                } else if (pathLen > max2) {
                    max2 = pathLen;
                }
            }
        }
        
        diameter = max(diameter, max1 + max2);
        return {max1, diameter};
    }
    
    long long diameter;
    
public:
    TreeDiameter(int vertices) : n(vertices), diameter(0) {
        adj.resize(n);
    }
    
    void addEdge(int u, int v, long long weight = 1) {
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight});
    }
    
    // Method 1: Two BFS
    long long getDiameterBFS() {
        if (n == 0) return 0;
        
        // First BFS to find one endpoint
        auto [node1, dist1] = bfs(0);
        
        // Second BFS to find other endpoint
        auto [node2, diameter] = bfs(node1);
        
        return diameter;
    }
    
    // Method 2: One DFS
    long long getDiameterDFS() {
        if (n == 0) return 0;
        
        diameter = 0;
        dfs(0, -1);
        return diameter;
    }
    
    // Get diameter path
    vector<int> getDiameterPath() {
        if (n == 0) return {};
        
        auto [node1, dist1] = bfs(0);
        
        // Modified BFS to record path
        vector<long long> dist(n, -1);
        vector<int> parent(n, -1);
        queue<int> q;
        q.push(node1);
        dist[node1] = 0;
        
        int node2 = node1;
        long long maxDist = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (auto [v, weight] : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    q.push(v);
                    
                    if (dist[v] > maxDist) {
                        maxDist = dist[v];
                        node2 = v;
                    }
                }
            }
        }
        
        // Reconstruct path
        vector<int> path;
        int current = node2;
        while (current != -1) {
            path.push_back(current);
            current = parent[current];
        }
        
        return path;
    }
};

// Centroid decomposition
class CentroidDecomposition {
private:
    int n;
    vector<vector<int>> adj;
    vector<bool> removed;
    vector<int> subtreeSize;
    
    // Calculate subtree size
    int calculateSize(int u, int parent) {
        subtreeSize[u] = 1;
        for (int v : adj[u]) {
            if (v != parent && !removed[v]) {
                subtreeSize[u] += calculateSize(v, u);
            }
        }
        return subtreeSize[u];
    }
    
    // Find centroid
    int findCentroid(int u, int parent, int treeSize) {
        for (int v : adj[u]) {
            if (v != parent && !removed[v] && subtreeSize[v] > treeSize / 2) {
                return findCentroid(v, u, treeSize);
            }
        }
        return u;
    }
    
    // Decomposition process
    void decompose(int u, int parent) {
        int treeSize = calculateSize(u, -1);
        int centroid = findCentroid(u, -1, treeSize);
        
        removed[centroid] = true;
        
        // Process centroid
        processCentroid(centroid);
        
        // Recursively decompose subtrees
        for (int v : adj[centroid]) {
            if (!removed[v]) {
                decompose(v, centroid);
            }
        }
    }
    
    // Process centroid logic (customizable)
    void processCentroid(int centroid) {
        cout << "Processing centroid: " << centroid << endl;
        
        // Add specific processing logic here
        // Example: calculate paths through centroid
    }
    
public:
    CentroidDecomposition(int vertices) : n(vertices) {
        adj.resize(n);
        removed.resize(n);
        subtreeSize.resize(n);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void decompose() {
        fill(removed.begin(), removed.end(), false);
        decompose(0, -1);
    }
};

// Virtual tree construction
class VirtualTree {
private:
    int n, timer;
    vector<vector<int>> adj;
    vector<int> depth, parent, tin, tout;
    vector<vector<int>> up; // Binary lifting
    
    void dfs(int u, int p, int d) {
        tin[u] = timer++;
        depth[u] = d;
        parent[u] = p;
        up[u][0] = p;
        
        for (int i = 1; i < up[u].size(); i++) {
            if (up[u][i-1] != -1) {
                up[u][i] = up[up[u][i-1]][i-1];
            }
        }
        
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
        
        tout[u] = timer++;
    }
    
    bool isAncestor(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
    
    int lca(int u, int v) {
        if (isAncestor(u, v)) return u;
        if (isAncestor(v, u)) return v;
        
        for (int i = up[u].size() - 1; i >= 0; i--) {
            if (up[u][i] != -1 && !isAncestor(up[u][i], v)) {
                u = up[u][i];
            }
        }
        
        return up[u][0];
    }
    
public:
    VirtualTree(int vertices) : n(vertices), timer(0) {
        adj.resize(n);
        depth.resize(n);
        parent.resize(n);
        tin.resize(n);
        tout.resize(n);
        
        int logN = 0;
        while ((1 << logN) <= n) logN++;
        up.assign(n, vector<int>(logN, -1));
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void preprocess(int root = 0) {
        timer = 0;
        dfs(root, -1, 0);
    }
    
    // Build virtual tree
    vector<vector<int>> buildVirtualTree(vector<int>& important) {
        if (important.empty()) return {};
        
        // Sort by DFS order
        sort(important.begin(), important.end(), [&](int a, int b) {
            return tin[a] < tin[b];
        });
        
        // Add LCA nodes
        vector<int> nodes = important;
        for (int i = 0; i < important.size() - 1; i++) {
            int l = lca(important[i], important[i + 1]);
            nodes.push_back(l);
        }
        
        // Remove duplicates and sort
        sort(nodes.begin(), nodes.end());
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
        sort(nodes.begin(), nodes.end(), [&](int a, int b) {
            return tin[a] < tin[b];
        });
        
        // Build virtual tree
        vector<vector<int>> vtree(n);
        vector<int> stack;
        
        for (int u : nodes) {
            while (!stack.empty() && !isAncestor(stack.back(), u)) {
                stack.pop_back();
            }
            
            if (!stack.empty()) {
                vtree[stack.back()].push_back(u);
            }
            
            stack.push_back(u);
        }
        
        return vtree;
    }
};

int main() {
    // Test tree diameter
    TreeDiameter td(6);
    td.addEdge(0, 1, 2);
    td.addEdge(1, 2, 3);
    td.addEdge(1, 3, 1);
    td.addEdge(3, 4, 4);
    td.addEdge(3, 5, 2);
    
    cout << "BFS method diameter: " << td.getDiameterBFS() << endl;
    cout << "DFS method diameter: " << td.getDiameterDFS() << endl;
    
    vector<int> path = td.getDiameterPath();
    cout << "Diameter path: ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i];
        if (i < path.size() - 1) cout << " -> ";
    }
    cout << endl;
    
    // Test centroid decomposition
    CentroidDecomposition cd(7);
    cd.addEdge(0, 1);
    cd.addEdge(1, 2);
    cd.addEdge(1, 3);
    cd.addEdge(3, 4);
    cd.addEdge(3, 5);
    cd.addEdge(5, 6);
    
    cout << "Centroid decomposition:" << endl;
    cd.decompose();
    
    // Test virtual tree
    VirtualTree vt(8);
    vt.addEdge(0, 1);
    vt.addEdge(0, 2);
    vt.addEdge(1, 3);
    vt.addEdge(1, 4);
    vt.addEdge(2, 5);
    vt.addEdge(2, 6);
    vt.addEdge(6, 7);
    
    vt.preprocess(0);
    
    vector<int> important = {3, 4, 7};
    vector<vector<int>> vtree = vt.buildVirtualTree(important);
    
    cout << "Virtual tree construction completed" << endl;
    
    return 0;
}