Tree Distances and Diameter

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// BFS on an unweighted tree from a start node.
5
// Fills dist and parent arrays and returns the farthest node from start.
6
int bfs_far(const vector<vector<int>>& g, int start, vector<int>& dist, vector<int>& parent) {
7
    int n = (int)g.size() - 1; // assuming 1-indexed nodes
8
    dist.assign(n + 1, -1);
9
    parent.assign(n + 1, -1);
10
    queue<int> q;
11
    dist[start] = 0;
12
    q.push(start);
13
    int far = start;
14
    while (!q.empty()) {
15
        int u = q.front(); q.pop();
16
        if (dist[u] > dist[far]) far = u;
17
        for (int v : g[u]) {
18
            if (dist[v] == -1) {
19
                dist[v] = dist[u] + 1; // unweighted: each edge increases distance by 1
20
                parent[v] = u;
21
                q.push(v);
22
            }
23
        }
24
    }
25
    return far;
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    int n; // number of nodes
33
    if (!(cin >> n)) return 0;
34
    vector<vector<int>> g(n + 1);
35
    for (int i = 0; i < n - 1; ++i) {
36
        int u, v; cin >> u >> v;
37
        g[u].push_back(v);
38
        g[v].push_back(u);
39
    }
40
41
    vector<int> dist, parent;
42
    // 1) From an arbitrary node (1), find the farthest node a
43
    int a = bfs_far(g, 1, dist, parent);
44
    // 2) From a, find the farthest node b and distances
45
    int b = bfs_far(g, a, dist, parent);
46
    int diameter_length = dist[b];
47
48
    cout << "Diameter length (in edges): " << diameter_length << "\n";
49
    cout << "One pair of diameter endpoints: " << a << " " << b << "\n";
50
51
    return 0;
52
}
53

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int bfs_far(const vector<vector<int>>& g, int start, vector<int>& dist, vector<int>& parent) {
5
    int n = (int)g.size() - 1;
6
    dist.assign(n + 1, -1);
7
    parent.assign(n + 1, -1);
8
    queue<int> q;
9
    dist[start] = 0;
10
    q.push(start);
11
    int far = start;
12
    while (!q.empty()) {
13
        int u = q.front(); q.pop();
14
        if (dist[u] > dist[far]) far = u;
15
        for (int v : g[u]) if (dist[v] == -1) {
16
            dist[v] = dist[u] + 1;
17
            parent[v] = u;
18
            q.push(v);
19
        }
20
    }
21
    return far;
22
}
23
24
int main() {
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
28
    int n; cin >> n;
29
    vector<vector<int>> g(n + 1);
30
    for (int i = 0; i < n - 1; ++i) {
31
        int u, v; cin >> u >> v;
32
        g[u].push_back(v);
33
        g[v].push_back(u);
34
    }
35
36
    vector<int> dist, parent;
37
    int a = bfs_far(g, 1, dist, parent);
38
    int b = bfs_far(g, a, dist, parent); // parent[] now stores the tree of BFS from a
39
40
    // Reconstruct diameter path from b back to a using parent[]
41
    vector<int> path;
42
    for (int cur = b; cur != -1; cur = parent[cur]) path.push_back(cur);
43
    // path is b -> ... -> a (reverse of the path from a to b)
44
    reverse(path.begin(), path.end()); // now a -> ... -> b
45
46
    int L = (int)path.size() - 1; // number of edges on the path
47
    int radius = (L + 1) / 2;     // ceil(L/2)
48
49
    cout << "Diameter length: " << L << "\n";
50
    cout << "Radius: " << radius << "\n";
51
52
    if (L % 2 == 0) {
53
        // single center at the middle index
54
        int center = path[L / 2];
55
        cout << "Number of centers: 1\n";
56
        cout << "Center: " << center << "\n";
57
    } else {
58
        // two centers at the two middle indices
59
        int c1 = path[L / 2];
60
        int c2 = path[L / 2 + 1];
61
        cout << "Number of centers: 2\n";
62
        cout << "Centers: " << c1 << " " << c2 << "\n";
63
    }
64
65
    return 0;
66
}
67

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct LCA {
5
    int n, LOG;
6
    vector<vector<int>> g;
7
    vector<int> depth;
8
    vector<vector<int>> up; // up[k][v] = 2^k-th ancestor of v (or -1)
9
10
    LCA(int n) : n(n) {
11
        g.assign(n + 1, {});
12
    }
13
14
    void add_edge(int u, int v) {
15
        g[u].push_back(v);
16
        g[v].push_back(u);
17
    }
18
19
    void build(int root = 1) {
20
        // compute LOG = ceil(log2(n)) + 1
21
        LOG = 1;
22
        while ((1 << LOG) <= n) ++LOG;
23
        depth.assign(n + 1, -1);
24
        up.assign(LOG, vector<int>(n + 1, -1));
25
26
        // BFS to set depth and immediate parent up[0]
27
        queue<int> q;
28
        depth[root] = 0;
29
        up[0][root] = -1;
30
        q.push(root);
31
        while (!q.empty()) {
32
            int u = q.front(); q.pop();
33
            for (int v : g[u]) if (v != up[0][u]) {
34
                if (depth[v] == -1) {
35
                    depth[v] = depth[u] + 1;
36
                    up[0][v] = u;
37
                    q.push(v);
38
                }
39
            }
40
        }
41
        // Binary lifting DP
42
        for (int k = 1; k < LOG; ++k) {
43
            for (int v = 1; v <= n; ++v) {
44
                int mid = up[k - 1][v];
45
                up[k][v] = (mid == -1 ? -1 : up[k - 1][mid]);
46
            }
47
        }
48
    }
49
50
    int lift(int v, int steps) const {
51
        for (int k = 0; k < LOG && v != -1; ++k) {
52
            if (steps & (1 << k)) v = up[k][v];
53
        }
54
        return v;
55
    }
56
57
    int lca(int a, int b) const {
58
        if (depth[a] < depth[b]) swap(a, b);
59
        // Lift a to the depth of b
60
        a = lift(a, depth[a] - depth[b]);
61
        if (a == b) return a;
62
        // Lift both up together
63
        for (int k = LOG - 1; k >= 0; --k) {
64
            if (up[k][a] != up[k][b]) {
65
                a = up[k][a];
66
                b = up[k][b];
67
            }
68
        }
69
        // Now their parents are the LCA
70
        return up[0][a];
71
    }
72
73
    int dist(int a, int b) const {
74
        int w = lca(a, b);
75
        return depth[a] + depth[b] - 2 * depth[w];
76
    }
77
};
78
79
int main() {
80
    ios::sync_with_stdio(false);
81
    cin.tie(nullptr);
82
83
    int n; cin >> n;
84
    LCA solver(n);
85
    for (int i = 0; i < n - 1; ++i) {
86
        int u, v; cin >> u >> v;
87
        solver.add_edge(u, v);
88
    }
89
    solver.build(1); // root at 1 (any node works)
90
91
    int q; cin >> q;
92
    while (q--) {
93
        int u, v; cin >> u >> v;
94
        cout << solver.dist(u, v) << "\n";
95
    }
96
    return 0;
97
}
98

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int bfs_far(const vector<vector<int>>& g, int start, vector<int>& dist) {
5
    int n = (int)g.size() - 1;
6
    dist.assign(n + 1, -1);
7
    queue<int> q;
8
    dist[start] = 0;
9
    q.push(start);
10
    int far = start;
11
    while (!q.empty()) {
12
        int u = q.front(); q.pop();
13
        if (dist[u] > dist[far]) far = u;
14
        for (int v : g[u]) if (dist[v] == -1) {
15
            dist[v] = dist[u] + 1;
16
            q.push(v);
17
        }
18
    }
19
    return far;
20
}
21
22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    int n; cin >> n;
27
    vector<vector<int>> g(n + 1);
28
    for (int i = 0; i < n - 1; ++i) {
29
        int u, v; cin >> u >> v;
30
        g[u].push_back(v);
31
        g[v].push_back(u);
32
    }
33
34
    vector<int> distA, distB;
35
    // Find diameter endpoints a and b
36
    vector<int> tmp;
37
    int a = bfs_far(g, 1, tmp);
38
    int b = bfs_far(g, a, distA); // distA now holds distances from a
39
    bfs_far(g, b, distB);         // distB holds distances from b
40
41
    // Eccentricity of each node u is max(dist(u,a), dist(u,b))
42
    for (int u = 1; u <= n; ++u) {
43
        int ecc = max(distA[u], distB[u]);
44
        cout << ecc << (u == n ? '\n' : ' ');
45
    }
46
47
    return 0;
48
}
49