Submission #73702184

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
pair<int, int> dfs(int u, int parent, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    int max_len = 0;
    int far_node = u;
    for (int v : adj[u]) {
        if (v == parent) continue;
        auto [len, node] = dfs(v, u, adj, visited);
        len += 1;
        if (len > max_len) {
            max_len = len;
            far_node = node;
        }
    }
    return {max_len, far_node};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    while (Q--) {
        int N;
        cin >> N;
        vector<vector<int>> original_adj(N + 1);
        vector<int> degree(N + 1, 0);
        for (int i = 0; i < N - 1; ++i) {
            int a, b;
            cin >> a >> b;
            original_adj[a].push_back(b);
            original_adj[b].push_back(a);
            degree[a]++;
            degree[b]++;
        }
        vector<vector<int>> sub_adj(N + 1);
        for (int u = 1; u <= N; ++u) {
            if (degree[u] < 3) continue;
            for (int v : original_adj[u]) {
                if (degree[v] >= 3 && v > u) {
                    sub_adj[u].push_back(v);
                    sub_adj[v].push_back(u);
                }
            }
        }
        vector<bool> global_visited(N + 1, false);
        int max_x = 0;
        for (int u = 1; u <= N; ++u) {
            if (degree[u] >= 3 && !global_visited[u]) {
                vector<bool> vis(N + 1, false);
                auto [len1, node1] = dfs(u, -1, sub_adj, vis);
                for (int i = 1; i <= N; ++i) {
                    if (vis[i]) global_visited[i] = true;
                }
                fill(vis.begin(), vis.end(), false);
                auto [len2, node2] = dfs(node1, -1, sub_adj, vis);
                int diameter = len2 + 1;
                max_x = max(max_x, diameter);
            }
        }
        cout << max_x << '\n';
    }
    return 0;
}

Submission Info

Judge Result